[BaekJoon] #1697 숨바꼭질

문제이해

이 문제는 수빈이의 위치 N(0 ≤ N ≤ 100,000), 동생은 K(0 ≤ K ≤ 100,000)에 위치하고 있습니다.

수빈이는 자신의 위치에서 N+1, N-1, N*2 만큼 이동할 수 있는데, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구해 출력하면 되는 문제입니다.

문제접근

머릿속에 배열을 그려 상상해보면, 수빈이의 현재 위치에서 퍼져나가듯 탐색을 하게 되고, 동생을 찾는데에 걸리는 최단시간을 구해야 하므로, BFS를 생각했습니다.

문제 핵심

직선에서의 BFS, 방문배열을 int형으로 선언해 방문과 동시에 카운트 세어주기, 직선에서 이동 방법

2차원 배열에서 BFS 문제를 풀기 위해, 방향배열을 이용해주어 현재위치에서 이동할 다음 점의 좌표를 구하고, 해당 점이 board 내부인지 확인한 후, 방문 로직을 수행하는 방식이였습니다.

2차원에서의 움직임을 직선으로 바꾸어 유사하게 구현하면 됩니다.

우선, 방문처리를 위해 vistied[] 배열을 선언해주어야 합니다.

늘 방문처리 배열을 boolean으로 선언해주었지만, 이 문제에서는 방문과 동시에 초를 늘려 기록해주기 위해 int형으로 선언해주었습니다.

1-based으로 하기 위해 배열의 사이즈를 하나 크게 생성해주었습니다.

2차원 배열 BFS문제에서 이동을 위해 방향배열을 선언하고, for문을 이용해 x,y좌표를 계산하여 이동할 점의 좌표를 구했었는데, 이 문제에서도 유사하게 for문을 이용해 수빈이가 현재 위치에서 이동할 다음 점의 좌표를 구합니다.

이동할 점의 좌표를 구했으면 방문하기 전에, 해당 점이 문제에서 주어진 범위 내부의 점이고 아직 방문하지 않은 점인지 확인해주어야 합니다.

이 문제에서는 수빈이와 동생의 위치는 1000,000 을 넘어갈 수 없으므로, 아래와 같이 이동할 점의 위치가 문제에서 주어진 인덱스 내부에 위치하게 설정해주고, 방문하지 않아 visited[] 의 값이 0 인 인덱스만 방문할 수 있습니다.

아 너무 쉬운문제인데 어떻게 방문하는지도 다 그려지는데 1차원으로 바꿔놓으니 방문을 못하겠어 아는데 왜 쓰질 못하니의 표본
그냥 말그대로 다음 위치 계산하면 되는거였다 너무 이지한건데 ..

이제 일차원 bfs 나오면 다 맞출거에요

code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int visited[] = new int[100001];
    static int n,k;
    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());
        if(n==k) {
            System.out.println(0);
        }else {
            BFS(n);
        }
    }

    private static void BFS(int n){
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        visited[n] = 0;  // 수빈이의 처음 위치에서는 0초가 소요되므로 0으로 시작
        while(!q.isEmpty()){
            int now= q.poll();
            for(int i=0; i<3; i++){
                int next;
                if(i == 0){
                    next = now + 1;
                }else if(i == 1){
                    next = now - 1;
                }else{
                    next = now * 2;
                }

                if(next == k){
                    System.out.println(visited[now] + 1); // 동생을 찾았으므로 시간을 출력하고 종료
                    return;
                }
                // 다음 위치가 이동할 수 있는 범위 내부이고, 방문하지 않은 경우 방문처리 
                if(next >= 0 && next < visited.length && visited[next] == 0){
                    q.add(next);
                    visited[next] = visited[now] + 1;
                }
            }
        }
    }
}