게임 맵 최단거리

문제 링크

[프로그래머스] 게임 맵 최단거리

문제 풀이

문제 설명

(0,0)에 있는 캐릭터가 (n,m)에 있는 상대 팀 진영을 최단시간에 파괴하는 것이 목표이다.

문제 접근 방식

캐릭터와 상대 팀 진영이 정해져있기에, BFS를 통해 탐색할 수 있다고 생각했다.

문제 1

해당 방식을 고려한 코드는 아래와 같으나, 몇몇 테스트케이스에서 런타임 에러가 발생했다.

import java.util.*;
 
class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length;
        // visited 생성 후, -1로 채우기
        int[][] visited = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], -1);
        }
        visited[0][0] = 1;
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[] {0,0});
        
        int[] dy = {1,0,-1,0};
        int[] dx = {0,1,0,-1};
        while (!que.isEmpty()) {
            int[] curr = que.poll();
            int x = curr[1];
            int y = curr[0];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx]!=-1 || maps[ny][nx]==0) {
                    continue;
                }
                visited[ny][nx] = visited[y][x] + 1;
                que.add(new int[] {ny, nx});
            }
        }
        answer = visited[m - 1][n - 1];
        return answer;
    }
}

이유는 마지막 정답 부분에서 m과 n을 바꿔썼다…

answer = visited[m - 1][n - 1];

최종 코드

최종 코드는 아래와 같다.

import java.util.*;
 
class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length;
        // visited 생성 후, -1로 채우기
        int[][] visited = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], -1);
        }
        visited[0][0] = 1;
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[] {0,0});
        
        int[] dy = {1,0,-1,0};
        int[] dx = {0,1,0,-1};
        while (!que.isEmpty()) {
            int[] curr = que.poll();
            int x = curr[1];
            int y = curr[0];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx]!=-1 || maps[ny][nx]==0) {
                    continue;
                }
                visited[ny][nx] = visited[y][x] + 1;
                que.add(new int[] {ny, nx});
            }
        }
        answer = visited[n - 1][m - 1];
        return answer;
    }
}

정말 사소한 문제였으나, 원인을 파악하기까지 생각보다 많은 시간이 소모되었다. 다음부터는 이런 사소한 실수를 반복하지 않도록 주의해야 할 거 같다…