[알고리즘 | 프로그래머스] 게임 맵 최단 거리(BFS)
문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/1844
문제 요약
0 , 1로 구성된 N * M 형태의 배열이 주어진다. 0으로 주어진 위치는 접근할 수 없고 1로 주어진 위치로만 이동할 수 있다.
(0,0) 에서 (N-1, M-1) 까지 이동할 때 가질 수 있는 최단 경로를 구하는 문제이다.
입력 예시
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
입력 예시에 따른 출력
11
풀이 방법
처음에는 (0,0) 에서 )(N-1,M-1) 까지 내가 가볼 수 있는 모든 경로로 가보면 되는거 아닌가? 싶어 DFS로 아래와 같이 탐색을 진행했다.
희망회로를 돌려보았지만 효율성에서 시간초과가 발생헀다.
class Solution {
public int min_route = Integer.MAX_VALUE;
public int solution(int[][] maps) {
dfs(1,0,0,maps);
if (min_route == Integer.MAX_VALUE) return -1;
return min_route;
}
public void dfs(int current_route, int x , int y, int[][] maps){
// dfs 종료 조건
if (x < 0 || x > maps[0].length-1 || y < 0 || y > maps.length-1) {
return;
}
if ( maps[0].length - 1 == x && maps.length - 1 == y ){
min_route = Math.min(current_route, min_route);
return;
}
// 도달할 수 없는 길이거나 이미 방문했던 경로인 경우(Cycle 제거)
if ( maps[y][x] == 0 || maps[y][x] == -1 ){
return;
}
// 방문 표시
int temp = maps[y][x];
maps[y][x] = -1;
dfs(current_route+1,x,y-1,maps);
dfs(current_route+1,x-1,y,maps);
dfs(current_route+1,x+1,y,maps);
dfs(current_route+1,x,y+1,maps);
maps[y][x] = temp;
}
}
DFS는 위에서 말한대로 LEVEL 순으로 탐색하는게 아니라 깊이 우선 탐색이기 때문에 처음 (N-1,M-1)에 도달한 경로가 최단 경로가 아닐 수 있다. 그러나 DFS를 생각해보자. DFS는 같은 Level부터 탐색을 진행하고, 이전에 탐색을 진행했던 level과는 당연히 경로가 1차이 밖에 나지 않는다 (unweighted graph에서)
BFS는 아래 그림과 같이 Level1 > Level2 > Level3 를 순차적으로 탐색하고 레벨이 증가함에 따라 경로가 이전 레벨에 비해 1씩 증가하기 때문에, (N-1,M-1) 에 도달한 그 첫 경로가 결국 최단 경로이다. 반면 깊이 우선 탐색은 가능한 최대 깊이까지 탐색을 우선하기 때문에 첫번쨰로 목적지에 도달한 경로가 최소 경로가 아닐 수 있다. 결국 모든 경로를 다 해보고 min(current_route, min_route)를 비교하는 수 밖에 없다.
불필요한 탐색을 줄일 수 있다는 것이 무가중치 그래프에서 BFS 탐색을 진행하는 이유이다. 아래는 BFS로 변경하여 진행한 코드이다.
import java.util.*;
class Solution {
public static int min_route = Integer.MAX_VALUE;
public static int[] dx = {0,1,0,-1};
public static int[] dy = {-1,0,1,0};
public int solution(int[][] maps) {
return bfs(maps);
}
public static void main(String[] args) {
int[][] maps = {{1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1}};
}
public static int bfs(int[][] maps) {
int[][] distance = new int[maps.length][maps[0].length];
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(0,0));
distance[0][0] = 1;
maps[0][0] = -1 ;
while(!queue.isEmpty()){
Pair node = queue.remove();
int current_x = node.x;
int current_y = node.y;
// 도착 지점에 도달한 경우
if ( maps[0].length - 1 == current_x && maps.length - 1 == current_y ){
return distance[node.y][node.x];
}
for (int i=0; i<4; i++) {
// 범위를 벗어났거나 이미 방문했던 노드인 경우
int x = current_x + dx[i];
int y = current_y + dy[i];
if (!check(x, y, maps)) {
continue;
}
queue.add(new Pair(x, y));
distance[y][x] = distance[current_y][current_x] + 1;
maps[y][x] = -1;
}
}
return -1;
}
public static boolean check(int x, int y, int[][]maps){
// dfs 종료 조건
if (x < 0 || x > maps[0].length-1 || y < 0 || y > maps.length-1) {
return false;
}
// 도달할 수 없는 길이거나 이미 방문했던 경로인 경우(Cycle 제거)
if ( maps[y][x] == 0 || maps[y][x] == -1 ){
return false;
}
return true;
}
}
class Pair{
int x ; int y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
}
주의해야할 점
시간 초과
DFS > BFS로 변경했음에도 효율성 테스트에서 계속 실패했다. 그 이유는 즉시 방문처리를 해주지 않아서였다. 위의 코드는 queue에 삽입함과 동시에 maps[y][x] = -1 처릴 하여 즉시 방문 처리를 하고 있다.
이렇게 즉시 방문처리를 해주어야 다른 노드에서 방문을 시도할때 이미 queue에 들어간 노드를 다시 방문하지 않을 수 있다. 즉시 로딩에서 중요한 것은 "큐에 넣어준 바로 즉시 방문 처리를 한다." 는 것이다. 그래야 다시 큐에 동일한 노드를 넣지 않을 수 있다.
아래는 효율석 테스트에서 실패한 코드이다. 방문 처리를 현재 노드와 연결된 모든 노드를 큐에 넣어준 후 현재 노드에 대한 방문처리만 수행하니, 연결된 노느들은 방문처리가 되지 않고, 다른 노드를 방문했을때 중복적으로 queue에 들어가는 문제가 발생헀다. 아래 코드를 실행시켜 보면 효율성 테스트 4개에서 모두 실패하는 것을 볼 수 있다.
또 조금 창피한 얼탱 방구 없는 실수는 출력 함수를 안지웠다가 시간초과가 발생하기도 했다. 주의할 것 !!
import java.util.*;
class Solution {
public static int min_route = Integer.MAX_VALUE;
public static int[] dx = {0,1,0,-1};
public static int[] dy = {-1,0,1,0};
public int solution(int[][] maps) {
return bfs(maps);
}
public static void main(String[] args) {
int[][] maps = {{1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1}};
}
public static int bfs(int[][] maps) {
int[][] distance = new int[maps.length][maps[0].length];
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(0,0));
distance[0][0] = 1;
maps[0][0] = -1 ;
while(!queue.isEmpty()){
Pair node = queue.remove();
int current_x = node.x;
int current_y = node.y;
// 도착 지점에 도달한 경우
if ( maps[0].length - 1 == current_x && maps.length - 1 == current_y ){
return distance[node.y][node.x];
}
for (int i=0; i<4; i++) {
// 범위를 벗어났거나 이미 방문했던 노드인 경우
int x = current_x + dx[i];
int y = current_y + dy[i];
if (!check(x, y, maps)) {
continue;
}
queue.add(new Pair(x, y));
distance[y][x] = distance[current_y][current_x] + 1;
}
maps[current_y][current_x] = -1;
}
return -1;
}
public static boolean check(int x, int y, int[][]maps){
// dfs 종료 조건
if (x < 0 || x > maps[0].length-1 || y < 0 || y > maps.length-1) {
return false;
}
// 도달할 수 없는 길이거나 이미 방문했던 경로인 경우(Cycle 제거)
if ( maps[y][x] == 0 || maps[y][x] == -1 ){
return false;
}
return true;
}
}
class Pair{
int x ; int y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
}