백준

[백준] 1697번: 숨바꼭질 - JAVA

doomole 2025. 2. 5. 15:23
728x90
 

문제

 

 



풀이

문제에 주어진 최대값(100,000)의 Integer 배열(check)을 생성한다.

수빈이(N)와 동생(K)의 위치를 입력받는다.

queue를 생성하고 N을 추가한다.

check[N] 값을 1로 입력한다.

 

queue가 비어있을 때까지 반복하며 queue에서 값(q)을 꺼낸다.

3번 반복하며 q + 1, q - 1, q * 2 값(next)을 구한다.

next가 K인 경우 check[q]를 출력한다.

next가 최대값보다 작고, 0보다 같거나 크고, check[next]에 값이 0인 경우

check[q] + 1check[next]에 입력한다.

 

 

 

정답 코드

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

public class Main {
	static int N;
    static int K;
    static Queue<Integer> queue = new LinkedList<>();
    static int[] check = new int[100001];

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

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        queue.add(N);
        // N이 K인 경우
        if (N == K) {
            System.out.println(0);
        } else {
            queue.add(N);
            check[N] = 1;
            bfs();
        }
    }

    static void bfs() {
        while(!queue.isEmpty()) {
            int q = queue.poll();
            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) {
                    next = q + 1;
                } else if (i == 1) {
                    next = q - 1;
                } else {
                    next = q * 2;
                }
                if (next == K) {
                    System.out.println(check[q]);
                    return;
                }
                // next가 범위 내이고 아직 방문하지 않은 경우
                if (next >= 0 && next < check.length && check[next] == 0) {
                    queue.add(next);
                    check[next] = check[q] + 1;
                }
            }
        }
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.