📖Problem

🔍Intuition

DFS 의 의사코드를 토대로 구현할 수 있다.

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 내림차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

#24479. 알고리즘 수업 - 깊이 우선 탐색 1 (#24479. 알고리즘 수업 - 깊이우선탐색1)와의 차이는 인접 정점을 오름차순이 아닌 ‘내림차순’으로 방문한다는 것이다.

그래서 #24479 문제를 풀었다면 쉽게 접근할 수 있는 문제이다.

🔍Approach

🚩My submission

import sys
sys.setrecursionlimit(10**6) # 최대 재귀한도 깊이
input = sys.stdin.readline

def dfs(v):
    global order
    visited[v] = order  # 방문하면 순서 넣기
    order += 1          # 다음 순서로 넘어가기
    for u in sorted(graph[v]): # 오름차순으로 인접노드 방문하기 위해 정렬
        if visited[u] == 0: # 방문 안 한 노드면 dfs탐색
            dfs(u)

# n: 정점의 수, m: 간선의 수, r: 시작 정점
n, m, r = map(int, input().strip().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1) # 방문 순서 저장. 0이면 방문 X
order = 1

# m개의 간선 정보를 입력받아 그래프로 연결하기
for _ in range(m):
    u, v = map(int, input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

dfs(r)

# 해당노드를 몇 번째로 방문했는지 출력
for i in range(1, n + 1):
    print(visited[i])

1. 먼저 재귀로 탐색하기 때문에 **RecursionError**를 방지하기 위해 최대 재귀 한도 깊이를 설정해준다. 100,000으로 설정해준 이유는 문제에서 주어준 노드 n의 최댓값이 100,000이기 때문이다.
2. DFS 함수
   1. 방문할 경우, 방문 순서를 나타내는 order 변수를 visited 리스트에 대입하여 방문순서를 기록해준다.
   2. 그 다음 다음 순서로 넘어가기 위해 order 에 +1을 한다.
   3. 내림차순으로 인접 노드로 방문하기 위해서 해당 노드와 연결된 노드를 정렬시킨 후 for문으로 순회한다. 만약 순회한 노드가 방문하지 않은 노드라면 dfs 탐색을 시도한다.
3. 정점의 수 n, 간선의 수 m, 시작정점 r을 입력받고, 빈 그래프인 graph 리스트를 초기화한다.
4. visited 리스트는 1부터 n까지의 노드를 모두 0으로 초기화한다. 문제에서 방문할 수 없는 노드면 0을 출력하라고 했으므로 0으로 설정한다.
5. 그 다음 u, v입력받아 graph를 연결해준다.