문제 출처 : https://www.acmicpc.net/problem/24479
난이도 : 실버 2

---

문제 파악

N개의 노드, M개의 엣지, 그리고 방향과 가중치가 없는 그래프가 주어진다.

정점 R에서 시작하여 깊이 우선 탐색 으로 노드를 방문할 경우 노드의 방문 순서를 출력하라는 문제이다.

친절하게 깊이 우선 탐색 의사코드도 주어진다.

의사코드를 바탕으로 Python 코드로 변환하며 DFS를 적응해보면 좋을 것 같다.

수도코드

• visited 라는 배열을 만들어서 정점의 방문 여부를 True or False 로 저장해준다.
• 시작 정점 R의 인접 정점 집합을 오름차순으로 방문한다.
  - 만약 방문하지 않았다면, 파이썬에서는 visited 가 False 라면. 이 dfs 함수를 재귀적으로 호출해준다.

---

출력로직만 떠올려서 붙이면 되겠다 싶었는데 해답 코드가 생각보다 까다로웠다.

해결 로직

1. 입력

양방향 무가중치 간선은 다음과 같이 양쪽 인덱스에 값을 추가해주는 형식으로 받는다.

문제 조건대로 오름차순으로 정렬해준 모습이다.

2. visited 배열과 cnt 변수를 활용한 dfs 함수 정의

visited 코드에 몇번째로 방문했는지 cnt를 False 대신 넣어주어 풀 수 있다.

이유는 답을 출력해줄 배열을 하나 더 만들지 않고 visited 배열을 활용하기 위함이다.
그리고 False 대신 0을 넣어준 이유는 나중에 출력할때 방문하지 않은 노드는 0으로 출력해주기 위함이다.

graph[u]에 값이 방문하지 않았다면 재귀적으로 더 깊이 들어가게 된다.

3. 함수 호출 및 출력

dfs함수를 시작 노드 R부터 시작시켜주고, 다 돌고 나면 visited 배열의 저장된 cnt들을 차례로 출력해주면 방문 노드 흐름을 보는 것처럼 출력된다.

전체 해답 및 코드

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

N, M, R = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

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

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

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

dfs(R)

for i in range(1, N + 1):
    print(visited[i])