[Baekjoon] DFS - 24481 알고리즘 수업 - 깊이 우선 탐색 3

문제

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

 

풀이

1. 시작점으로 부터 모든 노드의 깊이(depth)를 구하는 문제

2. 깊이는 현재 노드의 깊이 + 1

 

예시

5 4 1
1 2
2 3
3 4
2 5

 

 

코드

import sys

sys.setrecursionlimit(130000)

n, m, r = map(int, sys.stdin.readline().rstrip().split())
edges = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    edges[x].append(y)
    edges[y].append(x)


for edge in edges:
    edge.sort()


def dfs(r, depth):
    visited[r] = depth

    for v in edges[r]:
        if visited[v] == -1:
            dfs(v, visited[r] + 1)


dfs(r, 0)
print(*visited[1:], sep="\n")