[백준] 13549 - 숨바꼭질 3

1. 문제

13549번: 숨바꼭질 3

2. 개요

동생과 숨바꼭질을 하고 있다.

현재 N의 위치에 있으며, 동생은 K의 위치에 있다. (0 ≤ N, K ≤ 100000)

N * 2의 위치로 순간이동, N + 1, N - 1의 위치로 걸어갈 수 있다.

순간이동에는 0초, 걷는 데에 1초의 시간이 소요된다고 할 때 동생을 찾는 데 걸리는 최소시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

힙, 우선순위 큐를 이용해 소요시간이 가장 짧게 걸리는 경우를 가장 먼저 탐색할 수 있도록 한다.

K의 위치에 도착했다면 현재까지 걸린 시간을 출력한다.

3-2. Python

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

q = [[0, N]]
visited = [False for i in range(100001)]
time, nowX = 0, N
visited[N] = True

while q and nowX != K:
    time, nowX = heapq.heappop(q)

    dests = [[time, nowX * 2], [time + 1, nowX + 1], [time + 1, nowX - 1]]

    for dest in dests:
        if dest[1] < 0 or dest[1] > 100000:
            continue

        if visited[dest[1]] == True:
            continue

        heapq.heappush(q, dest)
        visited[dest[1]] = True

print(time)

3-3. C#

namespace boj_13549
{
    internal class Program
    {
        class ArrayComparer : IComparer<int[]>
        {
            public int Compare(int[] x, int[] y)
            {
                if (x[0] != y[0])
                {
                    return x[0].CompareTo(y[0]);
                }
                else
                {
                    return x[1].CompareTo(y[1]);
                }
            }
        }

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]), K = int.Parse(input[1]);

            PriorityQueue<int[], int[]> q = new PriorityQueue<int[], int[]>(new ArrayComparer());
            q.Enqueue(new int[] { 0, N }, new int[] { 0, N });
            bool[] visited = new bool[100001];
            visited[N] = true;

            int time = 0;
            int nowX = N;

            while (q.Count > 0 && nowX != K)
            {
                int[] now = q.Dequeue();
                time = now[0];
                nowX = now[1];

                if (nowX == K)
                    break;
                    

                List<int[]> dests = new()
                {
                    new int[] { time, nowX * 2},
                    new int[] { time + 1, nowX - 1 },
                    new int[] { time + 1, nowX + 1 }
                };

                foreach (int[] dest in dests)
                {
                    if (dest[1] < 0 || dest[1] > 100000)
                        continue;

                    if (visited[dest[1]])
                        continue;

                    q.Enqueue(dest, dest);
                    visited[dest[1]] = true;
                }
            }

            Console.WriteLine(time);
        }
    }
}