문제

예제 입력 1

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

예제 출력 1

1
4
3
2
0

문제 이해

백준의 24479번 문제인 "알고리즘 수업 - 깊이 우선 탐색 1"과 거의 다를 게 없는 문제이다. 덕분에 쉽게 백준 랭크 10점을 얻었다. 이전 문제는 오름차순으로 정렬을 해서 탐색을 하지만 이번 문제는 내림차순으로 정렬하면 된다. 이전 문제에서 오름 차순으로 정렬을 따로 해줬었기 때문에 "reverse=True" 값만 넣어주면 문제가 풀린다.

알고리즘 수업 - 깊이 우선 탐색 1 - 정리글
https://velog.io/@junseong/%EB%B0%B1%EC%A4%80Python-24479%EB%B2%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1-%EC%8B%A4%EB%B2%84-2

예제 입력 1을 기준으로 만든 표와 자료

코드

# 백준 24480번 알고리즘 수업 - 깊이 우선 탐색 2
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(idx):
    global graph, visited, answer, order

    visited[idx] = True
    answer[idx] = order
    order += 1

    for i in graph[idx]:
        if not visited[i]:
            DFS(i)

# 0. 입력 및 초기화
N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
answer = [0] * (N+1)
order = 1

# 1. 연결 요소 입력
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. 내림차순 정렬
for i in range(1, N+1):
    graph[i].sort(reverse=True)

# 3. DFS호출
DFS(R) #idx

# 4. 출력
for i in range(1, N+1):
    print(answer[i])