너비 우선 탐색(BFS, Breadth-First Search)

이 문서의 내용

BFS는 하나의 정점에서 시작해 차례대로 모든 정점을 정확히 한 번씩 방문하는 알고리즘입니다.

이 알고리즘의 핵심은 어떤 노드를 방문했었는지 여부를 마킹하는 것입니다.

모든 정점을 정확히 한 번씩 방문해야하는 경우 사용합니다. 일반적으로 루트 노드를 정하고 인접한 노드를 순차적으로 탐색합니다.

• BFS는 두 노드 사이의 최단 경로를 찾을 때 사용합니다.
• 또는 좌표계에서 어떤 영역의 크기를 계산하기 위해서 사용합니다(아래 사진 참고, Programmers: PCCP 기출 문제 2번에서 발췌).

BFS를 구현하는 방법은 크게 두 가지입니다.

• 재귀 함수를 사용한 구현
• 큐(Queue) 자료 구조를 사용한 구현

일반적으로 큐를 사용하는 것이 성능면에서 유리하기 때문에 선호됩니다.

BFS 흐름도

BFS는 루트 노드를 Queue에 입력하는 것으로 시작됩니다. 이 과정은 깊이가 0인 노드를 탐색하는 과정입니다.

이제 Queue에 있는 노드(루트 노드)를 꺼내고 깊이가 1인 노드를 순차적으로 탐색하며 탐색이 완료되면 깊이를 늘려갑니다.

마찬가지로 탐색된 노드는 Queue에 입력됩니다.

노드 0을 Queue에서 꺼냅니다. 노드 0을 기준으로 인접한 노드를 순차적으로 탐색합니다.

노드 1 2 4가 탐색되었으며 순차적으로 Queue에 입력됩니다.

노드 1을 Queue에서 꺼냅니다. 인접한 노드는 이미 탐색 후 마킹되어 있어 노드 1을 기준으로 탐색 할 것이 없습니다.

노드 2를 Queue에서 꺼냅니다. 노드 2에 인접한 노드 3을 탐색 할 수 있습니다.

노드 3에서는 탐색 할 수 있는 인접 노드가 없습니다.

노드 3을 Queue에서 꺼냅니다. 인접한 노드는 모두 탐색되어 더 이상 탐색 할 것이 없습니다.

Queue에 남은 노드가 없습니다. 모든 노드가 탐색된 것으로 간주하고 종료합니다.

BFS가 완료되면 사진과 다음과 같은 탐색 경로가 만들어집니다.

이때 탐색 순서는 노드 0 1 2 4 3입니다. 

Step 1: 문제를 가정

일반적으로 BFS는 길 찾기 여러 개의 경로에 따른 점수 비교 등에 사용됩니다. BFS를 작성하기 전에 경로를 표현하는 컨테이너가 어떻게 문제로 주어지는지 중요합니다.

boolean[][] 이중 배열로 표현되는 격자가 있다고 가정합니다.

• 이중 배열에서 각 노드의 인덱스는 좌표를 의미합니다.
• 각 노드의 값은 true(이동 가능)와 false(장애물, 이동 불가)를 의미합니다.

예를 들어 위 격자는 {true, false, false} {true, true, true} {true, false, true} 이중 배열로 표현 할 수 있습니다.

Step 2: 노드의 좌표를 표현하는 클래스 작성

이중 배열로 표현되는 격자의 각 노드는 x, y 좌표 정보를 갖습니다.

public static class Node
{
	public int x;
	public int y;
		
	public Node(int x,
		    int y)
	{
		this.x = x;
		this.y = y;
	}
}

Step 3: Queue를 사용한 BFS 구현

BFS를 구현하기 위해 Queue 자료 구조를 사용합니다. 탐색된 노드는 Queue에 진입합니다.

현재 노드에서 더 이상 탐색할 수 있는 노드가 존재하지 않으면 큐에서 가장 먼저 입력된 노드를 꺼내서 BFS를 진행합니다.

동일한 노드는 재방문 될 수 없기 때문에 visited 플래그를 사용해 중복 방문을 방지합니다.

protected static void bfs(boolean[][] grid)
{
	int h = grid.length;
	int w = grid[0].length;
	int[] dx = new int[] { -1, 0, 1, 0 };
	int[] dy = new int[] { 0, -1, 0, 1 };
	boolean[][] visited = new boolean[h][w];
		
	java.util.Queue<Node> queue = new LinkedList<>();
	List<Node> result = new ArrayList<>();
		
	// 시작 노드 좌표
	int nx = 0, ny = 0;
	// 시작 노드를 방문합니다.
	visited[ny][nx] = true;
	queue.offer(new Node(nx, ny));
		
	// 큐가 빈 상태가 될때까지 반복합니다.
	while (!queue.isEmpty())
	{
		// 큐에서 가장 먼저 탐색된 노드 기준으로 주변을 탐색합니다.
		// 이때 큐에서 제거된 노드는 탐색 완료되었음을 의미합니다.
		Node node = queue.poll();
		result.add(node);
	
		// 탐색 방향은 노드 기준으로 4방향(좌,상,우,하 순서)입니다.
		for (int i = 0; i < 4; ++i)
		{
			// 탐색하려는 노드의 좌표입니다.
			nx = node.x + dx[i];
			ny = node.y + dy[i];
	
			// 격자를 벗어나는 경우는 탐색 할 수 없습니다.
			if (nx < 0 || ny < 0 || nx >= w || ny >= h)
				continue;
			// 장애물이 있는 노드는 탐색 할 수 없습니다.
			if (!grid[ny][nx])
				continue;
			// 이미 방문한 노드는 탐색 할 수 없습니다.
			if (visited[ny][nx])
				continue;

			// 탐색하려는 노드를 방문합니다.
			visited[ny][nx] = true;
			queue.offer(new Node(nx, ny));
		}
	}
    
	printResult(result);
}

코드		비고
Line 3:4	int h, w	격자의 너비(w)와 높이(h)를 구합니다.
Line 12:16	int nx = 0, ny = 0	임의의 시작 노드 xy(0, 0)를 선택합니다.
	visited[ny][nx] = true	임의의 시작 노드를 방문 상태로 만듭니다.
	queue.offer(...)	임의의 시작 노드를 Queue에 입력합니다.
Line 18:47	while (!queue.isEmpty())	Queue가 빈 상태가 될 때까지 반복합니다.
	Node node = queue.poll()	Queue에 가장 먼저 입력된 노드부터 차례대로 꺼냅니다.
	visited[ny][nx] = true	방문 가능한 노드를 방문 상태로 만듭니다.
	queue.offer(...)	방문 가능한 노드를 Queue에 입력합니다.