DFS와 BFS - 1260

1. 개요

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

코드 대부분은 다음 블로그를 참조했습니다: https://goplanit.site/42.%20Algorithm(1260_py)/

2. 코드

import sys
from collections import deque

# DFS
def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

# BFS
def bfs(n):
    visited[n] = True
    queue = deque([n])
    while len(queue) != 0:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, sys.stdin.readline().rstrip().split())
# graph, visited (1-indexed)
graph = [[] for _ in range(n+1)]
visited = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    graph[i].sort()

dfs(v)
visited = [False] * (n + 1)
print()
bfs(v)

3. 풀이 메모

1. 그래프 구성법

2차원 그래프 배열에 대해서 1차 인덱스가 노드(정점)을 의미하고, 그 1차 인덱스가 가리키는 1차원 배열이 연결된 노드를 의미한다. 문제에서는 양방향 그래프를 가정하고 있으므로 그래프 리스트에 두번 요소를 넣는다.

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

2. DFS 순회 방법

깊게 파고 들어가면 된다. 먼저 정점 노드(index = 1)에 연결된 노드들부터 하나씩 재귀적으로 탐색해 나간다. 이미 방문한 적이 있다면 별도로 파고 들어가지 않는다.

def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

3. BFS 순회 방법

정점 노드(index = 1)에 연결된 노드들을 하나씩 순회한다. 최상위 노드를 먼저 리스트에 넣은 상태로 큐를 만들어 초기화 하고, 루프 내부에서는 방문의 표시로 pop -> 프린트 한 뒤, 연결된 노드들을 하나씩 큐에 집어넣는다. 물론 방문한 전적이 있는 노드는 넣지 않아도 된다.

def bfs(n):
    visited[n] = True
    queue = deque([n])
    while len(queue) != 0:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

4. 코멘트

학부 수업에서 DFS, BFS 순회가 뭔지는 다 배웠지만, 구현은 직접 해본 적이 별로 없다. 최대한 빨리 알고리즘의 뼈대를 익히고 응용하는 것이 중요한 것 같다.