[백준] DFS와 BFS(1260)

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

문제에서 DFS와 BFS 탐색한 결과를 출력하는 프로그램을 작성해 보라고 하였다.

이전에 DFS는 설명했으니 생략하도록 하고, BFS에 대해 알아보도록 하자.

BFS(Breadth First Search), 우리나라 말로 너비 우선 탐색이라고 하며, 시작 노드에서 출발해 가장 가까운 노드를 기준으로 방문하면서 탐색하는 알고리즘이다.

BFS는 선입선출 방식으로 큐를 이용해 구현한다. 노드 수가 V, 에지 수가 E라고 하면 시간복잡도는 $O(V + E)$가 된다.

알고리즘을 설명하는 시간은 아니니 개념에 대한 자세한 내용은 생략하고 문제를 풀어보면서 함께 설명하는 방식으로 풀이하겠다.

BFS의 전체적인 동작을 슈도코드로 나타내면 다음과 같다.

# 시작 노드 push후 방문리스트 체크
queue.push(v)
visited[v] = True

# 큐가 비어있을떄까지 반복
while queue.isEmpty():
	# queue를 pop하여 현재 탐색을 진행할 노드 구하기
    node = queue.pop()
    print(node)
    
    # 현재 노드를 기준으로 인접한 노드를 push한 후 방문리스트 체크
    for i in A[node]:
    	if not visited[i]:
        	queue.push(i)
            visited[i] = True

Python

파이썬에서는 덱(Deque)을 이용해서 큐를 구현하므로 push할때는 append(), pop할때는 popleft() 메서드를 사용하면 된다.

따라서 전체 소스코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6)
from collections import deque

input = sys.stdin.readline
print = sys.stdout.write

mydeque = deque()
N, M, V = map(int, input().split())
A = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

# DFS 함수 재귀호출
def DFS(v):
    print(str(v) + " ")
    visited[v] = True

    for i in A[v]:
        if not visited[i]:
            DFS(i)

# 큐를 이용한 BFS 함수 구현
def BFS(v):
    # 시작 노드를 push
    mydeque.append(v)
    visited[v] = True

    # 큐가 비어있을때까지 반복
    while mydeque:
        # 먼저 pop을 통해 현재 노드 구하기 
        node = mydeque.popleft()
        print(str(node) + " ")

        # 현재 노드를 기준으로 인접한 노드를 push
        for i in A[node]:
            if not visited[i]:
                mydeque.append(i)
                visited[i] = True

for i in range(M):
    s, e = map(int, input().split())

    A[s].append(e)
    A[e].append(s)

# 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문해야 함
# 각 노드에 해당하는 인접리스트를 오름차순으로 정렬
for i in range(N + 1):
    A[i].sort()

DFS(V)
print("\n")

# DFS 종료 후 BFS 탐색을 위해 방문 리스트 초기화
visited = [False] * (N + 1)

BFS(V)

Java

자바에서는 큐를 사용하기 위해 Queue<Integer> queue = new LinkedList<>();와 같이 Queue<> 인터페이스를 구현한 LinkedList<> 구현체의 조합으로 사용한다.

push할때는 add() 메서드, pop할때는 poll() 메서드 사용한다.

따라서 문제풀이 방법은 다음과 같다.

import java.util.*;
import java.io.*;

public class P_1260 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        A = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            A[start].add(end);
            A[end].add(start);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(A[i]);
        }

        DFS(V);
        System.out.println();

        visited = new boolean[N + 1];

        BFS(V);
    }

    static void DFS(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i : A[v]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");

            for (int i : A[now]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

주의해야할 점은 DFS 종료 후 방문리스트가 모두 True로 설정되어있을 것이므로 BFS 실행 전에 모두 False로 초기화를 진행해주어야 한다.

또한 BFS 탐색은 특정 노드를 기준으로 탐색할 수 있는 경로가 여러개 존재할 수 있으므로 문제에서 방문할 수 있는 정점이 여러개인 경우 번호가 작은 것부터 탐색하라고 하였다.

따라서 각 노드에 해당하는 인접리스트를 오름차순으로 정렬하는 것도 잊지말자.