BOJ) 숨바꼭질

숨바꼭질

1697번: 숨바꼭질

풀이

 

가장 빠른 step에서 위치를 찾아야하기 때문에, step에 따라 우선순위 큐를 이용해야한다고 생각했다.

그래서 class spot을 만들어서 Comaparable을 implement해서 사용했었는데, 63%에서 계속 틀렸다.

설마 step에 따라서가 아닌가 싶어서 Queue로 바꿔서 제출해봤는데 63%에서 틀렸다.

결론은, 로직 자제가 틀렸던 것이다. 더불어, 우선순위 큐가 필요가 없던 것이다.

 

우선순위를 체크안해도 된다면, 굳이 우선순위 큐를 사용할 이유가 없기 때문에, 큐로 바꿔주었다.

이후에는 +1,-1,*2 움직이는 방법 세 가지를 배열에 저장했다.

3개 조건에 따라서 if문을 다르게 걸어주니까 생각하기가 복잡해서 배열로 바꿨다.

 

위에 두 사항만 바꾸니까 바로 통과했다.

아무래도 if문을 따로따로 설정할 때, 잘못 설정했던 것 같다.

 

아무튼 제출하고 보니까, 우선순위 큐가 아니라면 step과 index가 들어간 Spot 클래스가 필요 없다고 생각이 들었다.

최대 값이 100001기 때문에, boolean[] visit을 int[] steps로 바꿔주었다.

그리고 방문 체크하던 것을, 방문 체크와 동시에 step을 저장해주었다.

 

결론적으로 코드도 더 짧고, 메모리 효율도 아주 조금 더 나아졌다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class HideAndSeek_1697 { 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int left = Integer.parseInt(st.nextToken());
        int right = Integer.parseInt(st.nextToken());

        solution(left,right);

        br.close();

    }

    private static void solution(int left, int right) {
        final int MAX = 100001;
        int answer =0;
        boolean[] visit = new boolean[MAX];
        Queue<Spot> moveQ = new LinkedList<>();
        moveQ.offer(new Spot(left,0));

        int[] dx = new int[3];
        dx[0] = 1;
        dx[1] = -1;

        while(!moveQ.isEmpty()) {
            Spot spot = moveQ.poll();
            int idx = spot.idx;
            int step = spot.step;
            if(idx == right) {
                answer = step;
                break;
            }
            dx[2] = idx;
            step++;

            for(int i=0; i<3; i++) {
                int nx = idx + dx[i];
                if(nx >=0 && nx < MAX) {
                    if(!visit[nx]) {
                        visit[nx] = true;
                        moveQ.offer(new Spot(nx, step));
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

class Spot {
    int idx;
    int step;

    public Spot(int idx, int step) {
        this.idx = idx;
        this.step = step;
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class HideAndSeek_1697 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int left = Integer.parseInt(st.nextToken());
        int right = Integer.parseInt(st.nextToken());

        solution(left,right);

        br.close();

    }

    private static void solution(int left, int right) {
        final int MAX = 100001;
        int answer =0;
        int[] steps = new int[MAX];
        Queue<Integer> moveQ = new LinkedList<>();
        moveQ.offer(left);

        int[] dx = new int[3];
        dx[0] = 1;
        dx[1] = -1;

        while(!moveQ.isEmpty()) {
            int idx = moveQ.poll();
            if(idx == right) {
                answer = steps[idx];
                break;
            }
            dx[2] = idx;

            for(int i=0; i<3; i++) {
                int nx = idx + dx[i];
                if(nx >=0 && nx < MAX) {
                    if(steps[nx] ==0) {
                        steps[nx] = steps[idx]+1;
                        moveQ.offer(nx);
                    }
                }
            }
        }
        System.out.println(answer);
    }
}