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

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

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

알고리즘 수업 - 깊이 우선 탐색 1 문제

DFS를 이용하여 그래프를 직접 탐색해보는 문제

재귀를 활용하여 DFS를 구성하면 쉽게 해결 할 수 있다.

내가 푼 정답코드

def dfs(t):
    global cnt
    visited[t] = cnt
    line[t].sort()
    for i in line[t]:
        if visited[i] == 0:
            cnt += 1
            dfs(i)

import sys
sys.setrecursionlimit(150000)
N, M, R = map(int, sys.stdin.readline().split())
line = [[] for _ in range(N+1)]
visited = [0]*(N+1)  # 저장값
cnt = 1
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    line[a].append(b)  # 양 방향 간선
    line[b].append(a)  # 양 방향 간선
dfs(R)
for i in range(1, N+1):
    print(visited[i])

문제에서 주어진 조건대로 오르차순으로 정렬해주기 위해서 sort를 해주었다.

방문 순서를 체크해야 하니까 몇번대로 방문하는지 알기 위해서 cnt 변수를 통해 몇번 순서로 방문하는지를 visited에 넣어서 확인해주는 방법으로 구성하였다

---

느낀 점

DFS를 구성해보는 가장 기초적인 문제이다. 맨날 BFS만 연습하다가 DFS로 풀어보니 원리는 비슷한데 BFS만 하던 습관이 있어서 처음에는 헷갈렸던거 같다.

생각보다 DFS를 직접 구성해보는 연습을 하기에 좋은 문제였다