프로그래머스 121690번
https://school.programmers.co.kr/learn/courses/15009/lessons/121690

문제

---

생각하기

---

• BFS에서 점프를 했는지 안했는지 여부를 같이 체크하는게 중요하다.

동작

처음에 nextX, nextY를 생성하는 곳에서 신발사용과 신발 사용하지 않음을 구분하려고 했는데, 코드가 원하는대로 동작하지 않아서 한참 헤맸다.

이유는

        while(!que.isEmpty()) {
            Coordinate current = que.poll();
                        
            if(current.x == N && current.y == M) {
                return current.time;
            }
            
            for(int i=0; i<4; i++) {
                int nextX = current.x + dirX[i];
                int nextY = current.y + dirY[i];
                                
                
                // 신발사용하지 않음
                if(isAbleCheck(nextX, nextY, current.isUsed, isVisited) && map[nextX][nextY] != -1) {
                    que.offer(new Coordinate(nextX, nextY, current.isUsed, current.time + 1));
                    isVisited[nextX][nextY][current.isUsed] = true;
                }

          
                // 신발 사용
                if(current.isUsed == 0) {
                    nextX += dirX[i];
                    nextY += dirY[i];
                    if(isAbleCheck(nextX, nextY, 1, isVisited) && map[nextX][nextY] != -1 ) {
                        que.offer(new Coordinate(nextX, nextY, 1, current.time + 1));
                        isVisited[nextX][nextY][1] = true;
                    } 
                }
            }
        }

여기서 if(map[nextX][nextY] != -1) continue 조건을 달았는데, 여기서 첫번째 구멍에서 continue를 해버리면 점프도 못하고 지나간다는 걸 놓치고 있었음 그래서 해당 부분을 조건문 밖으로 따로 빼서 continue를 없애니까 해결할 수 있었다.

결과

코드

---

import java.util.*;

class Solution {
    public static int[][] map;
    public static int N, M;
    public static final int[] dirX = {-1, 1, 0, 0};
    public static final int[] dirY = {0, 0, -1, 1};
    
    public static class Coordinate {
        int x, y, dist, isJumped;
        
        public Coordinate(int x, int y, int dist, int isJumped) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.isJumped = isJumped;
        }
    } // End of Coordinate class
    
    public int solution(int n, int m, int[][] hole) {
        int answer = 0;
        
        input(n, m, hole);

        return BFS();
    } // End of solution()
    
    public int BFS() {
        boolean[][][] isVisited = new boolean[N + 1][M + 1][2]; 
        LinkedList<Coordinate> que = new LinkedList<>();
        
        que.offer(new Coordinate(1, 1, 0, 1));
        
        while(!que.isEmpty()) {
            Coordinate current = que.poll();
            
            if(!isAbleCheck(current.x, current.y, current.isJumped, isVisited)) continue;
            if(current.x == N && current.y == M) {
                return current.dist;
            }
            isVisited[current.x][current.y][current.isJumped] = true;
            
            for(int i=0; i<4; i++) {
                int nextX = dirX[i] + current.x;
                int nextY = dirY[i] + current.y;
    
                que.offer(new Coordinate(nextX, nextY, current.dist + 1, current.isJumped));                
                                
                if(current.isJumped == 1) {
                    nextX += dirX[i];
                    nextY += dirY[i];
                    que.offer(new Coordinate(nextX, nextY, current.dist + 1, 0));
                }
            }
        }
        
        return -1;
    } // End of BFS()
    
    public boolean isAbleCheck(int nextX, int nextY, int isJumped, boolean[][][] isVisited) {
        return nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= M && map[nextX][nextY] != 1 && !isVisited[nextX][nextY][isJumped];
    } // End of isAbleCheck()
    
    public void input(int n, int m, int[][] hole) {
        N = n;
        M = m;
        map = new int[N + 1][M + 1];
        
        for(int[] t : hole) {
            int x = t[0];
            int y = t[1];
            map[x][y] = 1;
        }
    } // End of input()
} // End of Solution class