[백준][Java] 1697번 : 숨바꼭질

[문제 링크]

https://www.acmicpc.net/problem/1697

문제 설명

수빈의 위치 N, 동생의 위치 K에 있고, 수빈이 이동해서 동생을 찾는다.

수빈의 위치가 X일 때 걸으면 1초 후에 X-1 또는 X+1, 순간이동하면 1초 후 2 * X

동생을 찾을 수 있는 가장 빠른 시간을 구한다.

 

 

 

 

문제 풀이

BFS로 풀이

걷거나 순간이동하는 것에 상관없이 수빈이가 이동할 수 있는 방법은 3가지이다.

• X + 1
• X - 1
• X * 2 

현재 수빈이의 위치에서 위 3가지 방법으로 이동할 수 있는 위치와 해당 위치로 이동하는 데 걸린 시간을 큐에 담는다.

이미 수빈이가 위치했던 곳은 중복해서 가지 않기 위해 boolean 배열 visited로 방문 체크한다.

큐에서 하나씩 꺼낼 때마다 동생의 위치 k와 같은지 비교해서 같으면 while문을 종료한다.

 

전체코드

import javax.print.attribute.IntegerSyntax;
import java.io.*;
import java.util.*;

class Pos {
    int x;
    int time;

    public Pos(int x, int time) {
        this.x = x;
        this.time = time;
    }
}

public class Main {

    static int n, k, result = 0;
    static boolean[] visited = new boolean[100001];

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

        n = Integer.parseInt(st.nextToken());   //수빈
        k = Integer.parseInt(st.nextToken());   //동생

        bfs();
        System.out.println(result);
    }
    public static void bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(n, 0));
        visited[n] = true;

        while (!q.isEmpty()) {
            Pos cur = q.poll();

            if (cur.x == k) {
                result = cur.time;
                return;
            }

            int x;
            for (int i = 0; i < 3; i++) {
                if(i == 0) x = cur.x - 1;
                else if(i == 1) x = cur.x + 1;
                else x = cur.x * 2;

                if(x >= 0 && x <= 100000 && !visited[x]) {
                    q.offer(new Pos(x, cur.time + 1));
                    visited[x] = true;
                }
            }
        }
    }
}

 

 

나의 실패 과정

1. DFS로 풀이

처음에는 DFS로 풀이했다가 StackOverFlow가 발생했다.

그냥 단순하게 현재 수빈의 위치에서 +1, -1, *2 한 값을 계속 재귀호출해서 K와 같을 경우에 종료하면 된다고 생각했다.

n=5, k=10인 경우, n*2 = 10으로 쉽게 찾을 수 있지만, 그렇지 않은 경우 100000 또는 0이 될 때까지 계속 재귀호출을 해야 한다.

 

2. BFS로 푸는데 큐에 있는 걸 전부 꺼낸다..?(왜그랬을까...2)

DFS로 풀 수 없다는 것을 깨닫고 큐를 사용하여 BFS로 풀고자 했다.

먼저 처음 수빈의 위치 N을 큐에 넣는다.

큐에 있는 모든 값을 꺼내고, 각 값의 N-1, N+1, N * 2 한 값을 큐에 넣는다. 그리고 시간 1 증가

이 방법을 반복해서 큐에 k가 존재할 경우 종료한다.

하지만 생각해보면 굳이 큐에 있는 모든 수를 다 꺼내서 각각  N-1, N+1, N * 2하고, 한 번에 시간을 1 증가할 필요가 없다.