[BOJ][백준] 13549 - 숨바꼭질 3

[문제 풀기]

13549번: 숨바꼭질 3

📒 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

📒 해결방법

이 문제는 출발지점과 도착지점을 주고 최소 시간을 찾는 문제이기 때문에 빠르게 다익스트라를 예측할  수 있는 문제이다. BFS로 최소시간을 찾으면서 visit로 방문처리를 하면서 경로를 움직이면 알아낼 수 있다.

📒 소스코드

package BOJ.Graph.dijkstra;

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

public class boj13549_숨바꼭질3 {
    static int N, K;
    static int[] dx = { -1, 1 };
    static boolean[] visit;
    static Queue<Pair> q;
    static int min = Integer.MAX_VALUE;
    // N의 최댓값은 100000이다.
    static int INF = 100000;

    static class Pair {
        int to;
        int cost;

        public Pair(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        // <= 100000이기때문에 +1해주기
        visit = new boolean[INF + 1];
        bfs();
        System.out.println(min);
    }

    static void bfs() {
        q = new LinkedList<>();
        q.offer(new Pair(N, 0));

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            visit[cur.to] = true;
            // 도착했을때의 최소시간..최소비용
            if (cur.to == K) {
                min = Math.min(min, cur.cost);
            }
            // 수빈이는 순간이동도 한다. cost는 변하지 않고 이동만 가능함.
            if (cur.to * 2 <= INF && visit[cur.to * 2] == false) {
                q.offer(new Pair(cur.to * 2, cur.cost));
            }
            // 수빈이의 위치는 X+1로 이동할수있다. 단, 방문하지 않았어야 함

            if (cur.to + 1 <= INF && visit[cur.to + 1] == false) {
                q.offer(new Pair(cur.to + 1, cur.cost + 1));
            }
            // 수빈이는 위치를 x-1로도 갈수있다. 단, 방문하지 않았어야 함
            if (cur.to - 1 >= 0 && visit[cur.to - 1] == false) {
                q.offer(new Pair(cur.to - 1, cur.cost + 1));
            }
        }
    }
}

📒 리뷰

내 제출

 

---

매일매일 알고리즘을 풀고 있지만, 프로젝트도 같이 진행하다 보니 사실 쉬운 것만 풀면서 잔디만 채우려고 했었다..
감 잃지 않게 내가 못 풀던 문제들도, 잘 해결하던 문제들도 같이 진행하며 해야겠다 ㅠㅠ
개발러들 다들 파이팅..🖥🖥🖥