[문제풀이] 백준 1697 숨바꼭질

 

 

 

알고리즘은 안 풀면 까먹는 것 같다.

BFS/DFS는 다른 유형에 비해 많이 풀어봤어서 손쉽게 풀 수 있을거라고 생각했는데

한 번에 성공하지 못했다. ^-^ 머쓱

 

 

백준 1697 숨바꼭질 문제

수빈이가 동생을 찾기 위해서 특정 이동 조건에 맞춰 탐색하는 문제이다.

전형적인 BFS 문제인 듯 하다.

 

< 이동 조건 >

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

이동 조건이 규칙적이므로 탐색 위치가 반복될 수 있는데 처음에 방문체크를 빼먹은 이유는…..!

그냥 잘못 생각했다.

설명하기도 어렵게 생각의 오류를 범해서 적기가 어렵다..

결론은

특정 지점에 도착했을 때, 그 지점에서 이동할 수 있는 모든 경우의 수(3가지 이동 조건)는 한 번에 큐에 넣어서 다음 단계로 나아가기 때문에 한 번 방문한 곳에 다시 돌아올 필요가 없다.

특히, 이 문제는 조건이 X-1 과 X+1 이라서 한 단계만에도 반복 방문이 가능하다.

예) 5에서 X-1 조건으로 이동하여 4로 갔고, 4에서 X+1 조건으로 움직이면 5

불필요한 탐색이랄까..?

아무튼 방문체크 넣어서 성공했다.

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

public class Main { // BOJ_1697_숨바꼭질

    static int n, k;
    static boolean[] visit = 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();
    }

    private static void bfs(){
        ArrayDeque<int[]> que = new ArrayDeque<>();
        que.offer(new int[] {n, 0});

        while (!que.isEmpty()){
            int[] tmp = que.poll();
            int cl = tmp[0]; //현재 위치
            int ct = tmp[1]; //현재 시간
            visit[cl] = true;

            if (cl == k){
                System.out.println(ct);
                break;
            }

            if (valid(cl-1)) {
                que.offer(new int[] {cl-1, ct+1});
            }
            if (valid(cl+1)) {
                que.offer(new int[] {cl+1, ct+1});
            }
            if (valid(cl*2)) {
                que.offer(new int[] {cl*2, ct+1});
            }
        }
    }

    private static boolean valid(int n){
        if(n < 0 || n > 100000 || visit[n]){
            return false;
        }
        return true;
    }
}

 

깨달은 점

알고리즘 좀 꾸준히 풀자~^-^