[Python] 백준/BOJ - 24479번: 깊이 우선 탐색 1

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

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

문제

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

예제 입력 1

5 5 1
1 4
1 2
2 3
2 4
3 4

예제 출력 1

1
2
3
4
0

풀이

고생한 흔적..

런타임 에러, 시간 초과가 계속 나서 꽤 어려움을 겪었다. 특히 재귀로 구현을 하면 런타임 에러(Recursion Error)가 발생하는데 해결하지 못해 재귀가 아닌 스택을 이용했다.

 

 

자세한 풀이와 설명은 아래 코드를 참조해주세요!

# 시간 초과 방지를 위해 sys와 deque 사용.
import sys
from collections import deque

input = sys.stdin.readline


def dfs(start):
    stack = deque()
    visited = [0 for _ in range(n + 1)]
    cnt = 1
    stack.append(start)

    while stack:
        v = stack.pop()
        if visited[v] == 0: # pop한 값의 visited값이 0이면(방문하지 않았다면)
            visited[v] = cnt # visited에 방문한 순서 cnt를 넣어줌.
            cnt += 1

            for i in graph[v]:
                if visited[i] == 0:
                    stack.append(i)

    return visited


n, m, r = map(int, input().split())  # 정점, 간선, 시작 정점
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for g in graph:
	# dfs의 스택에서 pop을 하면 뒤에서부터 꺼내오기 때문에 reverse해줘야 함.
    g.sort(reverse=True)

visited = dfs(r)

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