[Baekjoon] 1697 - 숨바꼭질

📝 문제

 

 

🔑 풀이 과정

되게 쉽게 봤다가 큰 코 다친 문제.

 

① 처음에 뭐에 홀린건지 DFS로 풀었다가 스택오버플로우 에러나면서 실패. 생각해보면 당연하다. 답이 없는 가지로 들어가면 끝까지 들어가니... 가장 빠른 시간(최소)을 찾는 문제이므로 BFS를 쓰자.

② 그다음 BFS로 풀었을 때 바로 틀렸습니다 받음... 반례를 찾아보니 처음 입력받은 N과 K가 같을 때(답이 0일때)를 고려하지 않았다. 기존코드는 val-1, val+1, val*2을 K와 비교하는 코드만 있었다. 코드를 수정해서 현재의 val과 K를 비교하게 만들었다.

//실패했던 반례

100000 100000 //출력: 0

③ 이게 나에게는 정말 찾기 힘들었던 부분인데, 한 번 들렀던 위치는 다시 큐에 추가하게끔 하면 안된다. (어차피 -1, +1, *2 연산을 반복하니까 하나의 위치는 한번만 추가하면 된다.). 즉, 방문배열을 써주자. 방문배열이 없었더니 했던 루트를 또 추가하고 또 추가하고를 반복해서 인지 아무리 기다려도 출력이 안되는 상황이 발생했다. (입력이 1일때를 생각하면 -1 계산시 0, +1 계산시 2, *2 계산시 2로 반복되는 값이 나온다. 한 루트는 버려도 된다.)

N, K의 범위가 0부터 100000까지로 주어진게 int를 초과하지 않는다는 힌트를 준거라 생각한건데, 배열 인덱스로 쓰라는 것이었나 보다.

//실패했던 반례

100 0 //출력: 100
0 100000 //출력: 22

 

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int K;

    static int ans;

    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //수빈이의 위치
        K = Integer.parseInt(st.nextToken()); //동생의 위치
        //입력 종료

        //BFS 수행
        BFS(0, N);

        //출력
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }

    static void BFS(int second, int n){
        Queue<int[]> queue = new LinkedList<>();
        visited[n] = true;
        queue.add(new int[] {second, n}); //현재 시간과, 현재 위치를 넣을 큐를 생성

        while(!queue.isEmpty()){
            int[] now = queue.remove();
            int time = now[0];
            int val = now[1];

            if(val == K){
                ans = time;
                return;
            }

            if(((val - 1) >= 0) && ((val - 1) <= 100000) && (!visited[val - 1])){
                visited[val-1] = true;
                queue.add(new int[] {time+1, val-1});
            }
            if(((val + 1) >= 0) && ((val + 1) <= 100000) && (!visited[val + 1])){
                visited[val+1] = true;
                queue.add(new int[] {time+1, val+1});
            }
            if(((val * 2) >= 0) && ((val * 2) <= 100000) && (!visited[val * 2])){
                visited[val*2] = true;
                queue.add(new int[] {time+1, val*2});
            }
        }
    }

}

- BFS 메서드 하단부분을 val-1은 0이상인지만, val+1, val*2는 100000이하인지만 검사해도 된다. val이 무조건 양수이기 때문이다.

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색