[백준] 1697: 숨바꼭질

문제

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

 

---

코드

import java.io.*;
import java.util.*;

public class bj_1697 {
    private static Queue<Integer> queue = new LinkedList<>();
    private static boolean[] visited = new boolean[100001];
    private static int K;

    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());
        K = Integer.parseInt(st.nextToken());

        int result = bfs(N);

        System.out.println(result);
    }

    private static int bfs(int v) {
        queue.add(v);
        visited[v] = true;
        int time = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int s = 0; s < size; s++) {
                int current = queue.poll();
                if (current == K) {
                    return time;
                }

                int[] dx = {current - 1, current + 1, current * 2};

                for (int nx : dx) {
                    if (nx >= 0 && nx <= 100000 && !visited[nx]) {
                        visited[nx] = true;
                        queue.add(nx);
                    }
                }


            }
            time++;

        }
        return time;
    }

}

---

풀이

queue.add(v);
visited[v] = true;
int time = 0;

• 큐에 초기값(`N`)을 삽입
• `visitied[v] = true` → 시작 위치를 방문 체크
• `time`: 경과 시간을 저장할 변수

 

int current = queue.poll();
if (current == K) {
    return time;
}

• 현재 큐에 있는 위치(`current`)를 가져옴
• 동생 위치(`K`)에 도달하면 `time` 반환

 

int[] dx = {current - 1, current + 1, current * 2};

for (int nx : dx) {
    if (nx >= 0 && nx <= 100000 && !visited[nx]) {
        visited[nx] = true;
        queue.add(nx);
    }
}

• 이동 가능한 3가지 경우
  • `current - 1` (뒤로 한 칸)
  • `current + 1` (앞으로 한 칸)
  • `current * 2` (순간이동)
• `if (nx >= 0 && nx <= 100000 && !visited[nx])`
  • 범위를 벗어나지 않고, 방문하지 않은 곳이면 큐에 추가

 

 

 

이제 BFS도 좀 익숙해져가는 듯하다... 처음에 문제를 보고 이걸 어떻게 풀어했는데 차근차근해보니깐 성공~~