넓이 우선 탐색은 주로 최단거리를 구할 때 사용한다.
기본 그래프는 아래와 같이 구성되는데, 넓이 우선 탐색은 깊이 우선 탐색과 달리 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에, 그래프를 레벨 탐색으로 진행한다.
- 1레벨 : 0번 노드
- 2레벨 : 1번 노드 -> 2번 노드
- 3레벨 : 3번 노드 -> 4번 노드 -> 5번 노드 -> 6번 노드
만약 0번 노드에서 3번 노드로 최소한의 이동했을 때, 최소 몇 번 이동하는지 생각해보자.
0번 노드는 1번 노드와 2번 노드로 이동할 수 있다.
만약 1번 노드로 이동한 경우 3번 노드와 4번 노드로 이동할 수 있다.
(최소 이동 거리는 2이다.)
만약 2번 노드로 이동한 경우 5번 노드와 6번 노드로 이동할 수 있는데, 2번 노드로 이동한 순간 3번노드로는 최단거리로 이동할 수 없다.
결국 최단거리를 찾기 위해서는 0번 노드에서 동시에 1번 노드와 2번 노드로 이동하고, 1번 노드에서 3번 노드와 4번 노드로 동시에 이동하면서 2번 노드도 5번 노드와 6번 노드로 동시에 이동하여 해당 노드가 목적지인지 확인해야 한다.
결국 레벨이 1씩 증가할 때, 그래프의 다음 깊이로 이동하고, 해당 깊이에서 목적지 노드가 있는지 확인하고 위와 같은 과정을 반복하면서 목적지 노드를 찾아야 최단거리를 구할 수 있다.
문제는 다음 레벨로 어떻게 동시에 움직일 수 있는가이다.
예시를 통해 문제를 해결해보자.
<예시 문제>
7 * 7의 격자판이 존재할 때, 출발점 격자인 (0,0) 에서 도착지인 (6,6) 까지 이동할 때의 최단거리를 구하시오.
격자의 값은 0과 1로 구성되는데, 0은 이동가능한 길이고, 1은 이동할 수 없는 벽이다.
격자판 입력 배열 예시
int[][] arr = {{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 1},
{1, 1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0},
{1, 0, 1, 0, 0, 0, 0}};
격자판을 만들기 위한 Point
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}- Point클래스를 만들어서 격자를 탐색할 노드 클래스를 만들어 준다.
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};- 상하좌우로 이동하기 위해 dx, dy 배열을 만든다.
public int solution(int[][] board) {
visited = new int[7][7];
queue = new LinkedList<>();
queue.offer(new Point(0, 0));
return bfs(0);
}-
처음 노드는 (0,0)에서 시작하기에, queue에 새로운 Point를 넣어준다.
-
그후 bfs를 돌려서 (6,6) 까지 최소 몇번 이동해야 하는지에 대한 값을 리턴한다.
1. Level과 Queue의 Size로 탐색하기
public int bfs(int L) {
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
Point poll = queue.poll();
for (int i = 0; i <= 3; i++) {
int nx = poll.x + dx[i];
int ny = poll.y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= 6 && ny <= 6 && visited[nx][ny] == 0) {
visited[nx][ny] = 1;
queue.offer(new Point(nx, ny));
if (nx == 6 && ny == 6) {
return L + 1;
}
}
}
}
L++;
}
return -1;
}-
처음 Queue에는 (0,0) 이 들어가 있다.
-
이후 Queue의 size만큼 queue에서 값을 꺼내서 그 값을 기준으로 상하좌우에 위치한 노드를 탐색하여 이동할 수 있는 노드면 노드를 queue에 다시 넣는 방식으로 진행된다.
-
위와 같은 진행을 자세히 보면 queue의 size만큼 for루프를 도는데, 해당레벨의 노드들만큼 도는 것을 알 수 있다.
-
루프를 4번 돌면서 nx와 ny를 새로 생성해 새로운 Point (상하좌우로 이동한 경우의 좌표) 를 Queue에 넣는 코드를 보면 다음 레벨의 노드들을 Queue에 모두 넣어 놓고, 다음 레벨 탐색을 진행할 때, 해당 레벨의 노드들의 갯수(size) 만큼 다시 루프를 도는 것을 볼 수 있다.
-
결국 Size를 사용하여 넓이 우선 탐색을 하는 것은 레벨을 이용하는 방식이다.
결론
레벨 탐색은 목적지 값을 찾을 때까지 같은 레벨의 노드들을 동시에 탐색하면서, 어떤 레벨에서 목적지 노드가 발견되면 바로 해당 레벨의 다음 레벨의 값을 리턴하여 최단거리를 구한다.
2. 이차원 배열 dir로 탐색하기
public int bfs(int L) {
while (!queue.isEmpty()) {
Point poll = queue.poll();
for (int i = 0; i <= 3; i++) {
int nx = poll.x + dx[i];
int ny = poll.y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= 6 && ny <= 6 && visited[nx][ny] == 0) {
visited[nx][ny] = 1;
queue.offer(new Point(nx, ny));
dir[nx][ny] = dir[poll.x][poll.y] + 1;
if (nx == 6 && ny == 6) {
return dir[nx][ny];
}
}
}
}
return -1;
}-
사실 우리의 목적은 최단 거리를 구하는 것이기 때문에, 굳이 Size를 고려하면서 Queue에서 값을 꺼낼 필요 없이, 계속 넣고 꺼내면서 이차원 배열 dir를 사용해, 어떤 노드로 갈 수 있는 최단거리 값을 넣어주면 된다.
-
처음 dir[0][0] = 0 이다.
((0,0) 으로 갈 수 있는 최단거리는 0이다.) -
노드 (x,y) 로 갈 수 있는 최단 거리를 구하는 방법은 (x,y)로 갈 수 있는 노드들 중에 가장 작은 값에 + 1을 해주면 된다.
-
어떤 순서쌍에서 (x,y)로 올 수 있는 값은 여러개가 존재할 수 있는데, 계속 Math.min()를 통해 갱신해주지 않는 이유는 위의 코드가 넗이 우선 탐색을 하기 때문에, 목적지의 값에 처음 도착하는 거리가 항상 최단거리로 보장되기 때문에, 다른 노드들의 최단거리는 무시해도 되기 때문이다.
결론
이차원 배열을 사용하여 최단거리를 구하는 경우, 처음 목적지 노드로 도착한 경우의 거리는 항상 최단거리로 보장된다.
