백준 24479 | DFS | 깊이 우선 탐색 1 [파이썬 python]

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 정점
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) # 방문 순서 저장. 0이면 방문 X

c = 1
def dfs(graph, v, visited):
    global c
    visited[v] = c # 방문하면 순서 나타내기
    
    for i in graph[v]:
        if visited[i] == 0: # 방문 안한 노드이면
            c += 1
            dfs(graph, i, visited) # dfs 재귀
            
# m개의 연결된 간선 정보 입력받기
for i in range(m):
    a, b = (map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)
# print(graph)

for i in range(n+1): # 오름차순으로 인접노드 방문하기 위해 정렬
    graph[i].sort()
# print(graph)

dfs(graph, r, visited)

for i in range(1, n+1):
    print(visited[i])

이 문제는 해당 노드를 몇 번째로 방문했는 지를 출력하는 문제이다.

 

먼저, dfs 함수를 살펴보면 방문 순서는 c를 이용하여 카운트를 하고, visited에 방문 순서를 기록해 주었다.

visited는 1부터 n까지의 노드를 모두 0으로 초기화하였다. 문제에서 방문할 수 없는 노드이면 0으로 출력하라고 했기 때문에 0으로 하였다.

 그다음으로 graph에서 1번 노드부터 dfs로 인접노드를 방문하여 해당 노드에 방문했으면 방문 순서를 기록해 주고,  방문하지 않은 노드이면 c+1을 하고 dfs 재귀한다.

 

간선 정보를 입력받는 부분은 다음과 같다.

문제에서 M개 줄에 간선 정보를 u, v형태로 입력받는다고 했으므로 for문을 m번 반복하여 입력받는다.

u, v는 서로 연결된 노드의 정보를 말한다. 따라서 1 4와 같이 입력되면 1번과 4번이 연결되어 있다고 하는 것이므로, graph[1]에 4를, graph[4]에 1을 추가해 줘야 각 노드에 연결된 모든 노드를 알 수 있다.

예제 입력과 같이 5개의 간선 정보를 입력받아 각 노드에 맞게 graph에 추가하면 graph는 오른쪽 사진과 같은 형태가 된다.

리스트의 특성상 0번부터 시작되므로 1번부터 n번노드에 대한 정보를 1번 인덱스에서 n번인덱스에 저장하기 위해 초기에 graph를 n+1개로 만들어준 것이다.(0번 인덱스는 무시한다.)

예제 입력에서 5번 노드에 대한 정보는 주어지지 않았기 때문에 graph[5]에는 정보가 없는 것이다.

모든 노드에 대한 인접 노드 정보를 입력받았으면, 문제에서 인접 노드는 오름차순으로 방문한다고 했으므로 각 노드의 인접노드 리스트를 오름차순 정렬 해준다.

준비과정이 완료되었으면 dfs를 실행한다.

 

마지막으로 결과 출력 부분은 다음과 같다.

visited 역시 graph와 같이 0번 인덱스는 무시하되 1번부터 n번 인덱스까지에 해당 노드의 방문 순서를 저장했다.

그러므로 for문을 통해 visited[1]부터 visited[n]까지의 값을 출력하면 된다.

이코테 DFS/BFS 강의를 듣고 백준에서 관련 문제를 풀어보았다.

처음이라 고난의 시간이 길었지만 조금씩 잘못된 부분을 수정해 가며 해결할 수 있었다.