[백준 문제풀이] 13023번 : ABCDE

https://www.acmicpc.net/problem/13023

13023번: ABCDE

💡 자료구조 시간에 배운 깊이우선탐색으로 푸는 문제

그렇지만 코드로 구현하니까 생각보다 이해가 잘 되지 않아 오랜시간 고민했다.

 

먼저 각 리스트의 인덱스는 사람을 의미(0, 1, 2, 3, 4, 5...)하고 그 인덱스의 리스트는 그 사람과 연결된 사람을 의미한다.

 

예를들어 [[4], [7], [7], [7, 4, 5], [7, 3, 6, 0], [3], [4], [1, 3, 4, 2]] 이면,

0은 4와 연결, 3은 7, 4, 5와 연결되어 있다는 의미이다.

 

여기서 visited를 활용해 해당 노드를 탐색했는지를 알 수 있게 하고 탐색하지 않았으면 재귀를 활용하여 연결된 노드를 확인한다. 

 

만약 예제 입력 4를 입력한다면 호출되는 dfs함수는 

dfs(0, 0)→dfs(4, 1)→dfs(7, 2)→dfs(1, 3)→dfs(3, 3)→dfs(5, 4) 이고

visited변수는 [True, False, False, True, True, True, False, True] 다음과 같이 끝난다.

 

✔ 소스코드

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

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

def dfs(idx, num):
    if num == 4:
        print(1)
        exit()
    for i in friend[idx]:
        if not visited[i]:
            visited[i] = True
            dfs(i, num + 1)
            visited[i] = False

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

print(0)