[Algorithm: BFS] 프로그래머스 <게임 맵 최단거리>

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

프로그래머스

 

---

문제 설명

2차원 맵에서 시작점 (0,0)에서 도착점 (n-1, m-1)까지 상하좌우로 이동하며 최단 거리를 구하는 문제이다.

• 1 → 이동 가능
• 0 → 벽 (이동 불가)

도착할 수 없다면 -1을 반환해야 한다.

 

처음 접근

처음에는 단순하게 모든 경로를 탐색하는 방식으로 접근하려 했다.

하지만 이 문제는 경우의 수가 많고 가장 중요한 것은 최단 거리이다.

 

어떻게 하면 가장 먼저 도착한 경로가 최단 거리라고 확신할 수 있을까?

 

---

 

핵심 아이디어

이 문제의 핵심은 다음과 같다.

가중치가 없는 그래프에서 최단 거리 → BFS

 

왜 BFS인가?

BFS는 탐색을 다음과 같은 순서로 진행한다.

• 거리 1
• 거리 2
• 거리 3

가까운 거리부터 차례대로 탐색한다. 따라서 어떤 좌표에 처음 도착한 순간, 그 경로는 이미 최단 거리이다.

 

DFS가 아닌 이유

DFS는 한 방향으로 끝까지 들어갔다가 돌아오기 때문에

• 먼저 도착했다고 해서
• 그 경로가 최단 거리라는 보장이 없다

 

---

BFS 설계

좌표 표현

int[] current = queue.poll();
int cx = current[0]; 
int cy = current[1];

 

배열에서는 maps[행][열] 구조이다.

 

방향 이동

 

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

 

방향의미

(-1, 0)	위
(1, 0)	아래
(0, -1)	왼쪽
(0, 1)	오른쪽

 

범위 체크

if (nx < 0 || nx >= maps.length || ny < 0 || ny >= maps[0].length)

 

 

거리 저장 방식

maps[nx][ny] = maps[cx][cy] + 1;

 

처음에는 이 부분이 이해가 안 됐다.

maps는 원래 0/1 배열인데, 왜 갑자기 거리 저장이 가능할까?

 

BFS를 시작하면 maps는 더 이상 지도가 아니라 거리 배열로 변한다

 

예를 들어

 

초기

1 0 1
1 0 1
1 1 1​

 

BFS 진행 후

1 0 5
2 0 4
3 4 5

 

 

각 칸의 값이 시작점에서의 거리가 된다.

 

 

---

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        boolean[][] visit = new boolean[maps.length][maps[0].length];
        return bfs(0, 0, maps.length - 1, maps[0].length - 1, maps, visit);
    }
    
    private int bfs(int x, int y, int targetX, int targetY, int[][] maps, boolean[][] visit) {
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{x, y});
        visit[x][y] = true;
        
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            
            if (cx == targetX && cy == targetY) {
                return maps[cx][cy];
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if (nx < 0 || nx >= maps.length || ny < 0 || ny >= maps[0].length) {
                    continue;
                }
                
                if (visit[nx][ny] || maps[nx][ny] == 0) {
                    continue;
                }
                
                visit[nx][ny] = true;
                maps[nx][ny] = maps[cx][cy] + 1;
                queue.offer(new int[]{nx, ny});
            }
        }
        
        return -1;
    }
}

 

 

정리

이 문제를 통해 얻은 가장 중요한 포인트는 3가지이다.

1. 최단거리 → BFS
2. BFS는 거리 순서대로 탐색한다
3. maps 배열을 거리 배열로 재사용할 수 있다

가중치 없는 최단거리 문제는 BFS로 풀고, 거리 배열은 기존 배열을 덮어써도 된다.