인프런 집으로 이동

문제

나의 풀이

import java.util.*;

public class GoHome {
    public static int solution(int[] pool, int a, int b, int home) {
        int check[][] = new int[2][10001]; // 0 : 앞으로 점프, 1 : 뒤로 점프
        for(int x : pool) { // pool 인 부분은 방문 할 수 없도록 모두 1로 표시
            check[0][x] = 1;
            check[1][x] = 1;
        }
        Queue<int[]> q = new LinkedList<>();
        check[0][0] = 1; // 시작점 표시
        check[1][0] = 1;
        q.offer(new int[]{0, 0});
        int L = 0; // 레벨
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) { // 현재 L레벨인 값들 모두 탐색
                int cur[] = q.poll();
                if(cur[0] == home) { // 현재 위치가 집에 도달한 경우
                    return L; // 점프 횟수 리턴
                }
                int nx = cur[0] + a; // 현재 위치에서 앞으로 점프
                if(nx <= 10001 && check[0][nx] == 0) { // 범위 안이면서 방문하지 않은 경우
                    check[0][nx] = 1; // 방문 표시
                    q.offer(new int[]{nx, 0}); // 앞으로 점프했으므로 순서쌍에 0 넣기
                }
                nx = cur[0] - b; // 현재 위치에서 뒤로 점프
                if(nx >= 0 && check[1][nx] == 0 && cur[1] == 0) { // 범위 안이면서 방문하지 않았으며 두번 연속 뒤로 점프가 아닌 경우
                    check[1][nx] = 1;
                    q.offer(new int[]{nx, 1}); // 뒤로 점프했으므로 순서쌍에 1 넣기
                }
            }
            // 이중 for문 다돌고나면 L+1레벨의 노드들만 큐에 남아있기 때문에 L을 증가시켜서 현재 레벨을 L+1로 만들어줌
            L++;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(GoHome.solution(new int[]{11, 7, 20}, 3, 2, 10));
        System.out.println(GoHome.solution(new int[]{1, 15, 11}, 3, 2, 5));
        System.out.println(GoHome.solution(new int[]{5, 12, 7, 19, 23}, 3, 5, 18));
    }
}

a를 이용하여 이동한 경우는 0을 순서쌍에 넣어주고 b를 이용하여 이동한 경우는 1을 순서쌍에 넣어주어 b를 두번연속 사용하지 못하게 구분해준다.
check 배열도 2차원 배열로 만들어서 앞으로 점프해서 온 경우는 check[0][i] = 1로 하고, 뒤로 점프해서 온 경우는 check[1][i] = 1로 구분해준다.
pool이 있는 부분도 check[0][pool] = 1, check[1][pool] = 1로 해주어서 이미 방문했다고 표시해주면 방문을 안할것이기 때문에 이렇게 구현해준다.
이동한 위치가 마이너스인 경우도 더뻗으면 안되기 때문에 컷해준다.

결과