1. 문제 설명

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

2. 문제 분석

재귀 또는 스택을 통해 DFS를 구현한다.

• 재귀 구현은 에러가 떠서 스택을 통해 구현했다. 스택을 통해 구현할 때 오름차순으로 연결 노드를 스택에 넣는데, 이때 넣는 순서를 주의하자.

3. 나의 풀이

import sys
from collections import deque

n, m, r = map(int, sys.stdin.readline().rstrip().split())

nodes = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
nodes_cnt = [0 for _ in range(n+1)]
for _ in range(m):
    tail, head = map(int, sys.stdin.readline().rstrip().split())
    nodes[tail].append(head)
    nodes[head].append(tail)

for i in range(n+1):
    nodes[i].sort(reverse=True)
cnt = 1
# def DFS(cur_node):
#     global cnt
#     visited[cur_node] = True
#     if nodes_cnt[cur_node] == 0:
#         nodes_cnt[cur_node] = cnt
#         cnt += 1
#     for next_node in nodes[cur_node]:
#         if not visited[next_node]:
#             DFS(next_node)

# DFS(r)

stack = deque()
stack.append(r)

while stack:
    cur_node = stack.pop()
    visited[cur_node] = True
    if nodes_cnt[cur_node] == 0:
        nodes_cnt[cur_node] = cnt
        cnt += 1

    for next_node in nodes[cur_node]:
        if not visited[next_node]:
            stack.append(next_node)


for cnt in nodes_cnt[1:]:
    print(cnt)