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

문제설명 1

문제설명 2

문제를 살펴보면 dfs(깊이 우선 탐색)을 구현하는 기본 문제이다

dfs(깊이 우선 탐색)이란, 트리나 그래프를 탐색하는 기법 중 하나인데, 시작 노드에서 자식의 노드들을

순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다 즉, 하나의 노드에서 3가지 갈래의 길이 있을 때

하나의 갈래를 선택한 후에 다시 돌아와서 다른 노드를 선택하는 것이 아니라 선택한 노드에서 계속해서 깊게

이루어진다는 것이다 그림판을 통해 설명을 하자면

해당 그림의 경우 1번에서 2번으로 간 후에 3번으로 가는게 아니라(2-1-3) 2번에서 4번으로 이동하게 된다

1번에서 2번을 탐색한 후에 3번을 탐색하는 것은 bfs(너비 우선 탐색)에 해당한다

 

해당 문제를 풀기 위한 간단한 의사코드도 존재한다 시작 정점에서 출발하여 깊이 우선 탐색으로 탐색을 함과 동시에

방문한 경우 흔적을 남기고 방문한 순서를 출력해야한다 이를 함수로 구현하면 다음과 같다

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

방문하지 않았다면 cnt의 값을 1증가함과 동시에 깊이 우선 탐색을 추가적으로 실시한다

(cnt는 방문 순서를 위해 존재하는 값) 문제에서 무방향 그래프라고 하였기 때문에 간선 정보가 주어지면

이를 양방향으로 추가해주어야한다 이후 시작지점부터 시작하도록 dfs(start)를 호출해주고

마지막에 visited리스트의 값을 출력해주면 된다(해당 위치에는 방문하지 않은 경우 0이, 방문하였다면 순서가 기록)

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

def dfs(idx):
    global cnt
    visited[idx] = cnt
    graph[idx].sort()
    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])

----- 추가 -----

(그림판을 통해 백준의 예제를 그래프로 구현한 모습)