백준: 13023 ABCDE

문제

13023번: ABCDE

 

문제 풀이

 그래프 탐색을 통해 연결된 관계에서 다음과 같은 관계를 이루는 경우가 있는가를 찾는 문제이다. DFS를 탐색 하는데 있어 시작 지점을 각 노드로 지정하여 탐색을 하면 된다. 백트랙킹이 필요하므로, `vistied` 체크/해제를 진행해주어야 정상적으로 경우의 수를 찾을 수 있다.

 

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

 

 즉, 이는 DFS로 탐색할 경우 depth가 4보다 큰 경우가 있는지를 찾는 것과 같다. 5명이 친구 관계를 이루어야 하지만 depth가 4인 경우까지만 찾으면 되는 이유는 depth가 0인 경우, 즉 자신을 제외하고 나머지 4명이 연결되었는지 탐색하면 되기 때문이다.

 

False True False False True
True False True False False
False True False True False
False False True False False
True False False False False

 

 문제는 DFS를 작성하면 되기에 어려운 것이 없었는데... 기존과 같이 그래프를 초기화 했을 경우 문제가 발생하였다. 기존에는 그래프를 N * N 크기의 2차원 리스트를 만들고 방문 가능한 경우 True로 표시하여 탐색하였다. 예를 들어 예제 입력 1의 경우 위와 같이 초기화하였다. 하지만 이렇게 할 경우 9%에서 시간 초과가 발생하여 넘어가지 않는다.

 

 다른 사람들의 풀이를 참고하니, 애초에 방문 가능한 노드만 추가해두는 방식을 사용한다는 것을 알 수 있었다. 따라서 그래프를 초기화 할 때 방문 가능한 노드만 추가하니, 탐색의 경우의 수가 줄어들어서 그런지 무사히 통과하였다.

 

코드

from sys import stdin


def dfs(depth, cur_node):
    if depth == 4:
        print(1)
        exit()

    for next_node in graph[cur_node]:
        if not visited[next_node]:
            visited[next_node] = True
            dfs(depth + 1, next_node)
            visited[next_node] = False


if __name__ == "__main__":
    n, m = map(int, stdin.readline().split())
    graph = [[] * n for _ in range(n)]
    visited = [False] * n

    for _ in range(m):
        i, j = map(int, stdin.readline().split())
        graph[i].append(j)
        graph[j].append(i)

    for node in range(n):
        visited[node] = True
        dfs(0, node)
        visited[node] = False

    print(0)

  depth가 4가 된다면, 경우의 수를 찾은 것이므로 더 이상 진행하지 않고 1을 출력하고 `exit()`를 통해 종료한다. 이와 반대로 모든 노드의 탐색을 진행하였음에도 찾지 못한다면, 만족하는 경우의 수가 없는 것이다.