[python] 백준 > DFS > ABCDE

[문제]

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

 

 

www.acmicpc.net/problem/13023

13023번: ABCDE

 

[나의 풀이]

import sys

N, M = map(int, input().split())
arr = [[] for _ in range(N)]
visited = [False] * N

# 그래프를 인접 리스트 방식으로 담는다.
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    arr[a].append(b)
    arr[b].append(a)


# dfs 깊이가 4이면 return 1
def dfs(n, depth):
    visited[n] = True

    if depth >= 4:
        print(1)
        exit(0)

    for k in arr[n]:
        if not visited[k]:
            dfs(k, depth+1)
            visited[k] = False


for i in range(N):
    if not visited[i]:
        dfs(i, 0)
        visited[i] = False

print(0)

 

- 인접리스트 방식으로 담는 법을 처음 알았다.

- dfs함수에 숫자를 넣을 n과 함께 depth가 어느정도인지 알 수 있도록 두가지 파라미터를 넘겨준다.

- dfs를 호출한 다음 다시 visited를 false로 해야하는지 처음에 이해가 안갔는데, 하나의 주기가 끝나고 다음 주기를 탐색할 때 다시 visited가 false로 초기화 돼있어야 갯수를 잘 셀수 있었다.

 

 

[다른 사람의 풀이]

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

adj_lst = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    adj_lst[a].append(b)
    adj_lst[b].append(a)

visited = [False for i in range(n)]

def dfs(v, depth):
    global ans
    visited[v] = True
    if depth >= 4:
        ans = True
        return
    for nxt in adj_lst[v]:
        if not visited[nxt]:
            dfs(nxt, depth + 1)
            visited[nxt] = False

ans = False
for i in range(n):
    dfs(i, 0)
    visited[i] = False
    if ans:
        break
print(1 if ans else 0)

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
rel = [list(map(int, input().split())) for _ in range(M)]
sort_rel = {}
for i in range(0, N):
    sort_rel[i] = []

global friend
zero = True


def isFriend(k):
    friend.append(k)
    print('friend : ', friend)
    if len(friend) == 5:
        return True
    # for v in dic[k]:
    #     if v not in friend:
    #         return isFriend(v, dic)
    #     else:
    #         pass
    for v in sort_rel[k]:
        if v not in friend:
            ans = isFriend(v)
            friend.remove(v)
            if ans == 1:
                return ans


for x, y in rel:
    sort_rel[x].append(y)
    sort_rel[y].append(x)


for key in sort_rel.keys():
    friend = []
    if isFriend(key):
        print(1)
        zero = False
        break
if zero:
    print(0)