[바킹독 알고리즘] 0x09강:BFS in 다차원 배열

BFS: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

그래프에서의 BFS 예시

0,0부터 시작해 방문했다는 표시를 남긴다.

0,0과 상하좌우 인접한 칸을 방문했다는 표시를 남기고 큐에 좌표를 넣는다.

현재 큐의 front와 상하좌우 인접한 좌표들을 보고 방문하지 않은 파란색이면 방문을 한 뒤 큐에 담는다. 과정을 반복한다.

사진만으로 이해가 어렵다면 바킹독 알고리즘 영상을 직접 보면 이해가 더욱 쉬울 것이다.

정리

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.

2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행한다.

3. 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문표시를 남기고 해당 칸을 큐에 삽입한다.

4. 큐가 빌때까지 2번을 반복한다.

모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. 

BFS 구현 코드 ver C++

#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[502][502] = {
{1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란칸 0이 빨간칸
bool vis[502][502]; // 해당 칸 방문 여부 저장
int n = 7, m = 10; // n=행, m=열
int dx[4] = {1,0,-1,0 }; //상하좌우 네 방향
int dy[4] = { 0,1,0,-1 };
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int>> q;
    vis[0][0]=1;
	q.push({ 0,0 });
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		cout << '(' << cur.X << "," << cur.Y << ") -> ";
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖 (행 열 범위)
			if (vis[nx][ny] || board[nx][ny] != 1) continue; //이미 방문 or 파란칸 아닌
			vis[nx][ny] = 1; //(nx,ny) 방문 했음을 의미
			q.push({ nx,ny });
		}
	}
}

BFS 구현코드 ver Kotlin

fun main() {
    val input = BufferedReader(InputStreamReader(System.`in`))
    val board = Array(502) { IntArray(502) }
    val visited = Array(502) { BooleanArray(502) }
    var tokenizer = StringTokenizer(input.readLine(), " ")
    var n = tokenizer.nextToken().toInt()
    var m = tokenizer.nextToken().toInt()
    var queue: Queue<Pair<Int, Int>> = LinkedList()

    for (i in 0 until n) {
        tokenizer = StringTokenizer(input.readLine(), " ")
        for (j in 0 until m) {
            board[i][j] = tokenizer.nextToken().toInt()
        }
    } // 각 값 board에 담기
    
    visited[0][0] = true
    queue.offer(Pair(0,0))
    while(queue.isNotEmpty()){
    	bfs(queue,board,visited,n,m)
    }   
 }
 

fun bfs(
    queue: Queue<Pair<Int, Int>>,
    board: Array<IntArray>,
    visited: Array<BooleanArray>,
    n: Int,
    m: Int
) {
    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)
    val cur = queue.peek()
    queue.poll()
    for (dir in 0 until 4) {
        var nx = cur.first + dx[dir]
        var ny = cur.second + dy[dir]
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
        if (visited[nx][ny] || board[nx][ny] != 1) continue
        visited[nx][ny] = true
        queue.offer(Pair(nx, ny))
    }
}

구현에서 유의해야 할 점 3가지는 

1. 시작점을 방문하고 방문표시를 남겨야 한다.

2. 큐에 값을 push 할 때 방문 표시를 남겨야 한다는 점.

(큐에서 빼낼 때 방문했다는 표시를 남기면 같은 칸이 큐에 여러번 들어가게 되어 시간초과가 날 수 있다.)

3. 이웃한 원소가 범위를 벗어났는지에 대한 확인을 제대로 해야한다.

문제현황

연습 문제 ✔	1926	그림	정답 코드
연습 문제 ✔	2178	미로 탐색	정답 코드
연습 문제 ✔	7576	토마토	정답 코드
연습 문제 ✔	4179	불!	정답 코드
연습 문제 ✔	1697	숨바꼭질	정답 코드
기본 문제	1012	유기농 배추	정답 코드
기본 문제	10026	적록색약	정답 코드
기본 문제	7569	토마토	정답 코드
기본 문제	7562	나이트의 이동	정답 코드
기본 문제	5427	불	정답 코드
기본 문제	2583	영역 구하기	정답 코드
기본 문제	2667	단지번호붙이기	정답 코드
기본 문제	5014	스타트링크	정답 코드
기본 문제	2468	안전 영역	정답 코드
기본 문제	6593	상범 빌딩	정답 코드
응용 문제	2206	벽 부수고 이동하기	정답 코드
응용 문제	9466	텀 프로젝트	정답 코드
응용 문제	2573	빙산	정답 코드
응용 문제	2146	다리 만들기	정답 코드, 별해 1
응용 문제	13549	숨바꼭질 3	정답 코드, 별해 1
응용 문제	1600	말이 되고픈 원숭이	정답 코드
응용 문제	13913	숨바꼭질 4	정답 코드
응용 문제	14442	벽 부수고 이동하기 2	정답 코드
응용 문제	16933	벽 부수고 이동하기 3	정답 코드
응용 문제	16920	확장 게임	정답 코드
응용 문제	11967	불켜기	정답 코드
응용 문제	17071	숨바꼭질 5	정답 코드
응용 문제	9328	열쇠	정답 코드
응용 문제	3197	백조의 호수	정답 코드
응용 문제	20304	비밀번호 제작	정답 코드