[Programmers] PCCP 모의고사 2회 4번 - 보물 지도 - Java

문제

프로그래머스

 

풀이

진수가 보물이 위치한 곳을 찾아서 이동하는데, 직선으로 2칸을 뛰어넘을 수 있는 기회는 1번 사용해 보물이 위치한 곳으로 최단 거리를 이동하는 문제이다.

 

1. 배열을 선언한다.

지도 배열(구멍이 있는지 없는지 여부)

방문 배열(뛰어넘은 경우, 뛰어 넘지 않았을 경우)

 

2. 구멍의 위치를 기록한다.

마지막 인자 true -> 뛰어넘은 기회 사용

마지막 인자 false -> 뛰어넘은 기회 사용하지 않음

 

3. 큐를 만들어서 시작 위치와 경로 정보를 저장해서 bfs를 수행한다.

목적지를 만나면 최단 거리이므로, 바로 answer에 기록하고 while문을 빠져나온다.

 

3-1. 현재 경로 정보가 뛰어넘을 수 있는 기회를 사용했다면

visited[mx][my][1]에 true를 기록하면서, 점을 이동한다.

 

3-2. 현재 경로 정보가 뛰어넘을 수 있는 기회를 사용하지 않았다면,

visited[mx][my][0]에 아직 뛰어넘지 못한 경우로 점을 이동하고,

현재 방향 dx, dy 배열을 더하는 것에 2배를 이동시킨 후, visited[mx][my][1]에 뛰어넘은 경우로 점을 이동한다.

 

4. 최단 거리를 반환한다.

 

소스코드

import java.util.ArrayDeque;

class Solution {
    private static class Point {
        int x;
        int y;
        int dist;
        boolean isUsed;
        
        Point(int x, int y, int dist, boolean isUsed) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.isUsed = isUsed;
        }
    }
    
    private static final int HOLE = 1;
    
    private static final int[] dx = {1, -1, 0, 0};
    private static final int[] dy = {0, 0, 1, -1};
    
    public int solution(int n, int m, int[][] hole) {
        int[][] map = new int[n + 1][m + 1];
        boolean[][][] visited = new boolean[n + 1][m + 1][2];
        
        for (int i = 0; i < hole.length; i++) {
            map[hole[i][0]][hole[i][1]] = HOLE;
        }
        
        ArrayDeque<Point> queue = new ArrayDeque<>();
        
        queue.addLast(new Point(1, 1, 0, false));
        visited[1][1][0] = true;
        
        int answer = -1;
        
        while(!queue.isEmpty()) {
            Point cur = queue.removeFirst();
            
            if (cur.x == n && cur.y == m) {
                answer = cur.dist;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int mx = cur.x + dx[i];
                int my = cur.y + dy[i];
                
                if (mx < 1 || mx > n || my < 1 || my > m) continue;
            
                if (cur.isUsed) {
                    if (map[mx][my] != HOLE && !visited[mx][my][1]) {
                        queue.addLast(new Point(mx, my, cur.dist + 1, true));
                        visited[mx][my][1] = true;
                    }
                } else {
                    if (map[mx][my] != HOLE && !visited[mx][my][0]) {
                        queue.addLast(new Point(mx, my, cur.dist + 1, false));
                        visited[mx][my][0] = true;
                    }
                    
                    mx = cur.x + (2 * dx[i]);
                    my = cur.y + (2 * dy[i]);
                    
                    if (mx < 1 || mx > n || my < 1 || my > m) continue;
                    
                    if (map[mx][my] != HOLE && !visited[mx][my][1]) {
                        queue.addLast(new Point(mx, my, cur.dist + 1, true));
                        visited[mx][my][1] = true;
                    }
                }
            }
        }
        
        return answer;
    }
}

 

실행결과