[DFS/BFS] 백준 #1260 DFS와 BFS 프로그램 - Python

📚 문제

링크: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

💡 접근법

DFS와 BFS를 구현하는 문제이다.

DFS란?
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

BFS란?
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

💻 코드

1) 전체 코드

import sys
from collections import deque
sys.setrecursionlimit(10000)

N, M, V = map(int, sys.stdin.readline().split())

A = [[] for _ in range(N+1)]
dfs_visited = [False] * (N+1)
bfs_visited = [False] * (N+1)

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    A[a].append(b)
    A[b].append(a)

for i in range(N+1):
    A[i].sort()


def DFS(v):
    dfs_visited[v] = True
    print(v, end=' ')
    for i in A[v]:
        if not dfs_visited[i]:
            DFS(i)


def BFS(v):
    dq = deque()
    dq.append(v)
    bfs_visited[v] = True
    while dq:
        node = dq.popleft()
        print(node, end=' ')
        for i in A[node]:
            if not bfs_visited[i]:
                dq.append(i)
                bfs_visited[i] = True


DFS(V)
BFS(V)

 

2) 해설

(1) 패키지 Import

import sys
from collections import deque
sys.setrecursionlimit(10000)

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였고, 큐를 사용하기 위해 collections.deque 모듈을 임포트한다.

또한 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이므로 재귀의 최대 깊이를 10000으로 늘려주었다.

 

(2) 입력받기

N, M, V = map(int, sys.stdin.readline().split())

A = [[] for _ in range(N+1)]
dfs_visited = [False] * (N+1)
bfs_visited = [False] * (N+1)

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    A[a].append(b)
    A[b].append(a)

노드의 개수(N), 엣지의 개수(M), 탐색을 시작할 노드의 번호(V)를 입력받고, 인접 리스트(A)와 방문 리스트(dfs_visited, bfs_visited)를 초기화한다.

엣지의 개수만큼 for문을 순회하면서 인접 리스트를 생성한다.

이때, 입력으로 들어오는 엣지는 양방향이므로 양방향 엣지로 구현한다.

 

(3) 엣지 정렬

for i in range(N+1):
    A[i].sort()

문제에서 방문할 수 있는 노드가 여러 개일 경우에는 노드 번호가 작은 것을 먼저 방문하라고 제시했으므로 각각의 엣지를 오름차순 정렬한다.

 

(4) DFS 구현

def DFS(v):
    dfs_visited[v] = True
    print(v, end=' ')
    for i in A[v]:
        if not dfs_visited[i]:
            DFS(i)

인자로 들어온 노드에 대해 방문 리스트를 체크하고, 이는 탐색한 노드가 되므로 현재 노드를 출력한다.

해당 노드에 대한 인접 리스트의 요소들 중 방문하지 않은 노드에 대해 재귀 방식으로 DFS를 수행한다.

 

(5) BFS 구현

def BFS(v):
    dq = deque()
    dq.append(v)
    bfs_visited[v] = True
    while dq:
        node = dq.popleft()
        print(node, end=' ')
        for i in A[node]:
            if not bfs_visited[i]:
                dq.append(i)
                bfs_visited[i] = True

deque()를 생성하고 현재 노드를 큐에 삽입한다.

현재 노드에 대해 방문 리스트를 체크하고 큐가 빌 때까지 while 문을 수행하기 시작한다.

 

큐에서 노드를 꺼내고 이는 탐색한 노드가 되므로 출력한다.

해당 노드에 대한 인접 리스트의 요소들 중 방문하지 않은 노드를 큐에 삽입하고 방문 리스트를 체크한다.

 

(6) 출력하기

DFS(V)
BFS(V)

각각의 함수 내에서 탐색 경로를 출력한다.

 

✅ 정답 확인

 

---

 

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^