[백준] 1697 숨바꼭질 - Java

문제 - 숨바꼭질

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

 

 

 

접근 방법

 

이 문제는 bfs 문제인데 1차원 배열로 푸는 bfs문제이다 

생각 보다 쉬운 문제이다 

시작점에서 +1, -1, *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 Main {
    static int N;
    static int K;
    static int[] map;
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[100001];
            map[N] = 1;
            queue.add(N);

            System.out.println(bfs());

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public static int bfs() {
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            if (poll == K) {
                return map[K] - 1;
            }
            if (poll - 1 >= 0 && map[poll - 1] == 0) {
                map[poll - 1] = map[poll] + 1;
                queue.add(poll - 1);
            }
            if (poll + 1 < 100001 && map[poll + 1] == 0) {
                map[poll + 1] = map[poll] + 1;
                queue.add(poll + 1);
            }
            if (poll * 2 < 100001 && map[poll * 2] == 0) {
                map[poll * 2] = map[poll] + 1;
                queue.add(poll * 2);
            }
        }
        return -1;
    }
}

---

문제 풀고 느낀점

 

이 문제는 bfs 문제를 응용한 문제인데 2차원 배열이 아닌 1차원 배열 문제이다 -> 신선했다

문제를 푸면서 처음 시작을 1로 시작을 해서 마지막 결과 값에 -1를 해주는 것을 깜빡하고 계속 왜 안되는거지? 라고 하면서 시간을 지체 했다....