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

백준 24479번 깊이 우선 탐색 1

코드 풀이

재귀 함수 풀이법

import sys
sys.setrecursionlimit(10**6)

N, M, R = map(int, sys.stdin.readline().split(' '))

graph = [[] * (N + 1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split(' '))
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    graph[i].sort()

#print(graph)
visited = [0] * (N + 1)
sequence_number = [0] * (N + 1)


def dfs(x):
    global cnt
    cnt += 1
    visited[x] = 1
    sequence_number[x] = cnt
    for i in graph[x]:
        if not visited[i]:
            dfs(i)


cnt = 0
dfs(R)

for i in sequence_number[1:]:
    print(i)

스택 풀이법

import sys
sys.setrecursionlimit(10**5)

N, M, R = map(int, sys.stdin.readline().split(' '))

graph = [[] * (N + 1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split(' '))
    graph[a].append(b)
    graph[b].append(a)

#print(graph)
for i in range(N+1):
    graph[i].sort(reverse=True)

visited = [0] * (N + 1)
node_cnt = [0] * (N + 1)

cnt = 1
stack = []
stack.append(R)
visited[R] = 1

while stack:
    x = stack.pop()
    visited[x] = 1
    if node_cnt[x] == 0:
        node_cnt[x] = cnt
        cnt += 1
    for i in graph[x]:
        if not visited[i]:
            stack.append(i)

for i in node_cnt[1:]:
    print(i)