[파이썬, Python] 백준 24479: 알고리즘 수업 - 깊이 우선 탐색 1

문제

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

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

코드

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

n, m, r = map(int,input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
cnt = 1

for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for i in range(n+1):
    graph[i].sort()

def dfs(graph, v, visited):
    global cnt
    visited[v] = cnt
    for i in graph[v]:
        if visited[i] == 0:
            cnt += 1
            dfs(graph, i, visited)
dfs(graph, r, visited)

for i in range(n+1):
    if i != 0:
        print(visited[i])

설명

깊이 우선 탐색(DFS)을 처음으로 접했던 문제였다.

트리와 노드에 대해서 알아보고 문제를 풀이하게 되면 더 이해가 쉬울 것이다.

우선 n+1개로 이루어진 공백 리스트의 리스트를 만들어준다.(인덱스를 0이 아니라 1부터 세기 위함)
그리고 방문을 체크할 n+1개의 0으로 이루어진 리스트를 만들어준다.

그리고 노드 간의 연결 관계를 나타내기 위해 각 그래프의 리스트에 연결된 노드의 숫자를 넣어준다.

이후 연결 관계를 정리한 그래프를 sort 해준다.

그리고 dfs를 계산할 함수를 하나 만들어준다.
전역 변수 cnt를 이용하고 이는 방문 순서를 카운트한다.
v의 visited 리스트에 현재의 방문 순서를 뜻하는 cnt를 넣어준다.
이후 v와 연결된 i에 대해서 체크를 하게 되는데,
만약 i의 방문 기록이 없다면 cnt를 하나 올려주고 i에 대해서 dfs를 재귀하여 계산해 준다.
(연결된 노드의 끝부분까지 탐색을 하는 과정)

dfs 함수에 대해 시작 지점을 기준으로 실행해 준다.

이후 0이 아닌(사용하지 않은 인덱스) 방문 리스트에 대해서 출력해 준다.