13023. ABCDE (Python)

13023번: ABCDE

 

풀이

 dfs를 사용하여 깊이가 5인 경우가 있는지를 체크하면 된다. 방문체크 부분에서 주의할 건 재귀함수 내에서 방문했던 지점에 대해서 False 처리를 해줘야 한다는 것이다. 그렇지 않으면 모든 경로를 탐색할 수 없게 되어 깊이가 5인 경로가 있음에도 해당 경로를 찾지 못하는 반례가 생길 수 있다.

 

코드

import sys
input = sys.stdin.readline


# n: 현재 사람 번호, depth: 깊이
def dfs(n, depth):
    if depth == 5: # 깊이가 5인 지점에 도달하면 1출력하고 프로그램 종료 
        print('1')
        sys.exit(0)

    visited[n] = True
    for friend in graph[n]: # n번과 친구인 사람들에 대하여 dfs
        if visited[friend]:
            continue

        dfs(friend, depth + 1)
        visited[friend] = False # 방문 체크를 False로 설정해 모든 경로를 탐색할 수 있게 해준다.


if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(N):
        visited = [False for _ in range(N)]
        dfs(i, 1)

    print('0')