[Baekjoon]백준 24480 알고리즘 수업 - 깊이 우선 탐색 2(실버 2) - Python

문제설명 1

문제설명 2

이전에 풀이한 문제 백준 24479와 굉장히 유사한 문제이다 대신 문제에서 알려준 의사 코드를 보면

24479와 다르게 내림차순으로 정점 번호를 방문하는 것을 확인할 수 있다

 

문제 제출만 하는 것이 아니라 공부를 하는 것이 목적이므로 천천히 코드를 곱씹어보며 작성하였다

일단, 정점의 수, 간선의 수, 시작 정점을 받아온 후, 양방향 간선 정보를 받아온다

이 과정을 하기 위해 이전에 graph 리스트를 선언하여 입력받은 간선 정보를 저장하도록 해야한다

이후 dfs함수를 호출하면 되는데 해당 함수는 먼저 방문 순서를 기록해준다

cnt변수를 전역 변수로 선언하여 추가적으로 함수의 인자를 받지 않도록 하였다

이후 해당 위치에서의 graph를 내림차순으로 정렬하고 for문을 통해 방문하지 않은 곳을 찾아

방문함과 동시에 cnt 변수에 1을 더해주고 재귀적으로 dfs를 호출하면 된다

이후 for문을 통해 graph를 돌면서 방문 순서를 출력해주면 된다

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

def dfs(idx):
    global cnt
    visited[idx] = cnt # 방문 순서 기록
    graph[idx].sort(reverse=True) # 내림차순으로 정렬
    for i in graph[idx]:
        if visited[i] == 0:
            cnt += 1
            dfs(i)
    
vertex, edge, start = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
visited = [0] * (vertex+1)
cnt = 1

for _ in range(edge): # 양방향 간선 정보 입력
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(start)

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