[Baekjoon] 24479번 : 알고리즘 수업 - 깊이 우선 탐색 (Python, DFS)

[Baekjoon] 24479번 : 알고리즘 수업 - 깊이 우선 탐색 (Python, DFS)

 

목차

 

 

 

 

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

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

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 156168KB / 시간 588ms / 코드 길이 453B

 

그래프 간선에 따른 graph를 기입하고 이를 오름차순으로 변경한다.

또한, 방문 처리를 진행하는 visit list에 방문 횟수를 기입하여 DFS 처리를 진행하면 문제가 풀린다.

 

다만 본 문제를 처리할 때 유의해야할 점은 sys.setrecursionlimit을 설정해줘야한다는 점 그리고 counting을 할 때 유의해야한다.

 

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

def dfs(start):
    global cnt
    V[start] = cnt
    E[start].sort()

    for i in E[start]:
        if not V[i]:
            cnt += 1
            dfs(i)

n,m,r = map(int, input().split())
E = [[] for _ in range(n+1)]
V = [0]*(n+1)

for i in range(m):
    u, v = map(int, input().split())
    E[u].append(v)
    E[v].append(u)

cnt = 1
dfs(r)
for i in range(1, n + 1):
    print(V[i])