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

 

문제

https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

시간 복잡도

시간 복잡도는 재귀를 써서? 잘 모르겠지만 n^2 일거 같다.

 

코드

import sys
sys.setrecursionlimit(100000)
n, m, r = map(int, sys.stdin.readline().split())

graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
cnt = 1
visited_order = [0] * (n+1)
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
for i in range(len(graph)):
    graph[i].sort()


def dfs(r, graph, visited):
    global cnt
    visited[r] = True
    visited_order[r] = cnt
    cnt += 1
    for i in graph[r]:
        if visited[i] is not True:
            dfs(i, graph, visited)


dfs(r, graph, visited)

for i in visited_order[1:]:
    print(i)

해설

 

전형적인 dfs 문제인데 문제를 잘못 읽어서 고생했다. 하하

요구하는 사항이 뭔지 확실히 알고 접근하자.

다만 어려웠던게 재귀를 사용해서 제한을 거는 것에 꽤 많은 생각을 했다 

예전에 현대 문제를 풀때 알았던 것인데 그걸 활용해서 했다.