[백준] 1697 : 숨바꼭질

문제 출처: https://www.acmicpc.net/problem/1697

소요 시간: 시도(1h) + 풀이(30m)

---

문제

---

시도

 

처음엔 DFS를 시도해봤지만 바로 실패했다.

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

public class Main {

    private static int end;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 0 ~ 100,000
        end = Integer.parseInt(st.nextToken()); // 0 ~ 100,000

        System.out.print(solution(n));
    }

    private static int solution(int n) {
        if (n >= end) return n - end;

        // n이 움직일 수 있는 범위는 n-1, n+1, 그리고 2 * n이다.
        // 움직이는 지침은 어떻게 설정할까. 5에서 17로 이동한다 가정할 때
        // 예시에 따르면 5 10 9 18 17이 가장 최적이다.
        // 5에서 10으로 가는 건 당연하지만 거기서 1을 뺀 9로 가는 건 어떤 로직일까.
        /*
         10이 무작정 20으로 가는 것보다
         9의 2배인 18, 11의 2배인 22와 비교하여 17과 가장 가까운 것을 찾도록 한 것 같다.
         */
        if(2 * n <= end || Math.abs(2*n - end) <= 1) return 1 + solution(2 * n);
        else if (Math.abs(2 * (n-1) - end) < Math.abs(2 * (n + 1) - end)) return 1 + solution(n-1);
        else return 1 + solution(n+1);
    }
}

'5 17'의 경우 성공했지만, 그 외의 경우를 적용했을 때는 실패했기에 적확한 알고리즘은 아니었던 것 같아 조금 더 골몰했다.

 

20분 정도 고민해봤지만 맥을 못 잡아 다른 사람의 풀이를 잠깐 보고 BFS의 변형이라는 걸 알고 다시 시도해봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int end;
    private static int[] position;
    private static boolean[] visited;
    private static Queue<Integer> queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 0 ~ 100,000
        end = Integer.parseInt(st.nextToken()); // 0 ~ 100,000

        position = new int[2 * end];
        visited = new boolean[2 * end];
        queue = new ArrayDeque<>();

        bfs(n, 0);

        System.out.print(position[end]);
    }

    private static void bfs(int start, int idx) {
        position[start] = idx;
        visited[start] = true;
        queue.add(start);

        while (!visited[end] && !queue.isEmpty()) {
            int temp = queue.poll();

            if (temp != 0 && !visited[temp - 1]) bfs(temp-1, idx+1);
            if (2 * temp <= end && !visited[2 * temp]) bfs(2*temp, idx+1);
            if (temp + 1 <= end && !visited[temp + 1]) bfs(temp+1, idx+1);
        }
    }
}

 

결과는 실패였는데, 이유는 queue에 저장됐던 정수 temp가 도착점 end와 같아지는 경우를 고려하지 않았기 때문인 것 같다.

---

풀이

 

결국 다른 사람의 풀이를 참고하여 문제를 넘겼다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int end;
    private static int[] visited = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 0 ~ 100,000
        end = Integer.parseInt(st.nextToken()); // 0 ~ 100,000

        bfs(n);
        System.out.print(visited[end]-1);
    }

    private static void bfs(int start) {

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        int idx = start;
        int n = 0;
        visited[idx] = 1;

        while (!queue.isEmpty()) {
            n = queue.poll();

            if(n == end) return;
            if(n-1 >= 0 && visited[n-1] == 0) {
                visited[n-1] = visited[n] + 1;
                queue.add(n-1);
            }
            if(n+1 <= 100000 && visited[n+1] == 0) {
                visited[n+1] = visited[n] + 1;
                queue.add(n+1);
            }
            if(n*2 <= 100000 && visited[n*2] == 0) {
                visited[n*2] = visited[n] + 1;
                queue.add(n*2);
            }
        }
    }
}

 

참고 출처: https://smartpro.tistory.com/18

---

알게 된 점

 

DFS와 BFS를 그대로 쓰는 것만 할 줄 알고, 조금만 변형되면 못 푸는 것이 자괴감이 슬슬 온다.