Programmers 1844 - 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

간단한 bfs 문제이다.

상대 팀 진영에 ‘최대한 빨리’ 도착하는 것이 유리하다.

→ 최단거리 문제다. bfs를 통해서 최단 거리를 구할 수 있다.

주어진 데이터가 int [][] maps인데 0은 벽 1은 벽이 없는 자리를 나타낸다.

여기서 방문 가능한 점을 탐색하면서 bfs를 하면 된다.

또한 해당 맵에서 위치 값을 변경해 가면서 처리하면 별도의 방문 배열이 필요 없어진다.

import java.util.*;

class Solution {
    static int[] DR = {-1, 1, 0, 0}; // 상하좌우 기준
    static int[] DC = {0, 0, -1, 1};
    
    public int solution(int[][] maps) {
        
        int m = maps.length - 1;
        int n = maps[0].length - 1;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0}); // 시작점
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0];
            int c = curr[1];
            
            if (r == m && c == n) {
                return maps[r][c]; // 이미 도착지에 도달한 상황
            }
            
            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d];
                int nc = c + DC[d];
                
                if (nr < 0 || nr > m || nc < 0 || nc > n) continue;
                if (maps[nr][nc] != 1) continue;
                
                maps[nr][nc] = maps[r][c] + 1;
                q.add(new int[]{nr, nc});
            }
        }
        
        return maps[m][n] == 1 ? -1 : maps[m][n];
    }
}