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

💡문제접근

• 인접 정점은 오름차순으로 방문한다는 조건이 있었으므로 DFS 함수 내에서 인접 정점들을 오름차순으로 정렬하는 sort()를 넣어준다.
• 재귀를 사용해서 풀어야 하는 DFS, 재귀함수 문제라면, 아래의 코드를 상단에 쓰는 것은 선택이 아니라 필수이다.

>>> sys.setrecursionlimit(10**6)

💡코드(메모리 : 70564KB, 시간 : 612ms)

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

def DFS(graph, v, visited):
    global cnt
    visited[v] = cnt
    # 인접 정점 오름차순 정렬
    graph[v].sort()
    for i in graph[v]:
        if not visited[i]:
            cnt += 1
            DFS(graph, i, visited)

cnt = 1
N, M, R = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (N+1)
DFS(graph, R, visited)
for i in range(1, N+1):
    print(visited[i])

💡소요시간 : 10m