13023번: ABCDE (DFS/BFS)

13023번: ABCDE

문제의 조건에 맞는 A,B,C,D,E 가 존재한다는 것은 각 사람들을 노드로 두고, 친구관계를 갖는 두 사람을 연결하는 간선으로 그래프를 생각하면, 어떤 한 노드에서 시작해서 다른 노드로 이동할때 탐색 깊이가 4 이상이라는 것이다. 즉 DFS를 이용해 어느 한 노드에서부터 시작해 다른 노드를 탐색할 때 깊이가 4 이면 조건을 만족한다고 볼 수 있다. 따라서 처음에 아래와 같이 DFS 코드를 작성했다.

def dfs(v,graph,visited,depth):
    visited[v] = True
    # 만약 탐색 깊이가 4이면 가능
    if depth == 4:
        print(1)
        exit()
    for i in graph[v]:
        if not visited[i]:
            dfs(i,graph,visited,depth+1)

하지만 입력이 다음과 같다면,

5 5
0 1
1 3 
1 2
2 3
3 4

0 에서 부터 탐색을 하고  재귀 호출관계를 보면 (dfs(v,depth)라고 간단히 표현)

dfs(0,0)

      dfs(1,1)

           dfs(3,2)

                 dfs(2,3)

                 dfs(3,3)

이지만 0-1-2-3-4 로 탐색하면 문제조건을 만족한다.

dfs(0,0)

      dfs(1,1)

           dfs(3,2)

                 dfs(2,3)

                 dfs(3,3)

           dfs(2,2)

                 dfs(3,3)

                      dfs(4,4) 

따라서 아래와 같이 이미 탐색을 완료하였더라도 이전 depth에서 다른 경우를 탐색해보아야 한다. 즉 현재 depth에서의 방문체크를 초기화 해줄 필요가 있다. 그래야 dfs(2,2) 를 시행할 수 있으며 여기서 다시 dfs(3,3),dfs(4,4)를 실행할 수 있다. 

import sys 
sys.setrecursionlimit(100000) 

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

def dfs(v,graph,visited,depth):
    visited[v] = True
    # 만약 탐색 깊이가 4이면 가능
    if depth == 4:
        print(1)
        exit()
    for i in graph[v]:
        if not visited[i]:
            dfs(i,graph,visited,depth+1)
            # 방문체크를 다시 없애야 이전 노드들에서 해당 노드를 탐색가능
            visited[i] = False

for i in range(n):
    visited = [False] * n
    dfs(i,graph,visited,0)
print(0)