[BFS] 구현 및 팁

알고리즘 설명

가장 간단하게 설명하면 출발지에서 가까운 곳부터 방문하는 알고리즘으로

주로 최단 경로를 구할 때 많이 사용된다.

 

static int[][] board = {
    {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}
};

 

위와 같은 2차원 배열이 주어졌을 때, 현재 위치에서 자신의 상하좌우 칸을

큐에 넣어주어 가까운 순서대로 반복하며 탐색하는 방법을 사용한다.

 

이때 이미 방문했던 칸은 다시 방문하지 않기 위해

방문해주었다는 기록을 남겨주고

범위를 벗어난 경우와 해당하지 않는 경우도 탐색하지 않게 조심해야 한다.

 

구현

주어진 배열에서 끊기지 않고 이어질 때까지만 탐색하여

이어진 길이 몇 개인지 확인하고 싶은 경우를 생각해보자

 

 

눈으로 확인하면 당연히 10개인걸 알 수 있지만

BFS 알고리즘을 모르고 구현하려면 까다로운 문제다.

 

(0, 0) 위치를 기준으로 출발하였을 때,

0인 경우는 신경 쓸 필요가 없으니 1인 경우만 큐에 넣어주면서

가까운 순서대로 탐색을 해주면 된다.

 

static boolean[][] isVisited = new boolean[502][502];

 

이때 방문했던 칸은 다시 방문하지 않기 위해

방문 여부를 기록할 배열을 하나 선언해준다.

 

Queue<Pair> Q = new LinkedList<>();
isVisited[0][0] = true;
Q.offer(new Pair(0, 0));

 

시작점인 (0, 0)을 큐에 넣어주고, 방문했으니 방문여부를 true로 설정해준다.

 

private static class Pair {
    int x, y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

Pair 클래스는 x와 y 좌표를 기록하는 클래스다.

(2차원 배열을 사용해도 무방하다.)

 

while (!Q.isEmpty()) {
    Pair cur = Q.poll();
    
    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 (isVisited[nx][ny] || board[nx][ny] != 1) continue;
        
        isVisited[nx][ny] = true;
        Q.offer(new Pair(nx, ny));
    }
}

 

그 다음에는 큐가 비어있을 때까지 ( = 이어진 1이 더이상 없는 경우)

반복문을 돌아주면서 현재 위치의 상하좌우를 방문하며

1이 있는 경우만 큐에 넣어주고 방문여부를 true로 바꿔준다.

 

while문에서 처음 꺼낸 cur은 현재 위치가 되고

현재 위치의 좌표를 기준으로 for문을 4번 반복하여

각각 상하좌우를 탐색한다.

 

static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};

 

방향을 햇갈리지 않기 위해 이렇게 배열에 적어주는 것이 좋다.

dx[0], dy[0] 일 때는 x만 한칸 움직이고 y는 그대로니

현재 위치에서 오른쪽 칸을 탐색하고

나머지는 순서대로 아래, 왼쪽, 위를 탐색한다.

(탐색 순서는 상관 없다) 

 

전체 코드

public class BFS {
	static int[][] board = {
		{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}
	};

	static boolean[][] isVisited = new boolean[502][502];
    
	static int n = 7, m = 10;
    
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) {
		Queue<Pair> Q = new LinkedList<>();
		isVisited[0][0] = true;
		Q.offer(new Pair(0, 0));
        
		int count = 1;

		while (!Q.isEmpty()) {
			Pair cur = Q.poll();
            
			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 (isVisited[nx][ny] || board[nx][ny] != 1) continue;
                
				isVisited[nx][ny] = true;
				Q.offer(new Pair(nx, ny));
                count++;
			}
		}
        
        System.out.println(count);
	}

	private static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

팁

여러 개를 탐색하고 확인해야 하는 경우

 

위와 같이 길들이 총 몇 개 존재하고 길들의 길이는 몇인지 알고 싶은 경우에는

시작점이 몇 개인지 파악하고 각각의 시작점에서

그대로 while문을 통해 탐색을 해주면 된다.

 

2차원 배열을 이중 for문으로 돌아주면서

시작점이 될 수 있는 경우 BFS 알고리즘을 통해 탐색해주면 된다.

 

최단 거리를 구해야 하는 경우

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

위와 같은 2차원 배열이 주어졌을 때

(0, 0)에서 (4, 5)로 가는 최단 거리를 구해야 할 때는

기존에는 방문 여부를 기록했다면 출발지에서부터의

거리를 기록해주면서 방문 여부를 기록하면 된다.