[백준] 12851 - 숨바꼭질 2

1. 문제

12851번: 숨바꼭질 2

2. 개요

현재 위치 점 N과 목표 위치 점 K가 주어진다.

1초마다 현재 위치에서 +1, -1 *2의 위치로 이동할 수 있다.

점 N에서 점 K까지 가는 데 걸리는 최소 시간과 이동 방법의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

길이가 0 ~ 100000 이고 [방법의 수, 최소 시간]인 visited 배열을 만들어준다.

이 때 최소시간은 더 작은 값이 이미 들어와있다면 건너 뛸 것이므로 충분히 큰 값으로 채워넣는다.

현재 탐색할 수 있는 지역과 시간을 인자로 받는 bfs함수를 만든다.

현재 탐색할 수 있는 지역을 돌면서 다음에 탐색 가능한 지역을 하나씩 탐색한다.

만약 범위를 벗어나거나, 이미 더 짧은 시간에 탐색한 흔적이 있다면 건너뛴다.

이를 모두 통과했다면, 방법을 1만큼 늘리고, 시간을 갱신하고 리스트에 위치를 넣는다.

마지막으로 모든 가능한 위치가 담긴 리스트를 반환한다.

이 함수를 시간을 1씩 늘려가면서 visited[K]가 초기값이 아닐 때까지 반복한 후 답을 제출한다.

3-2. Python

import sys

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

def bfs(lst, idx):
    tmp = []
    for l in lst:
        dests = [l + 1, l - 1, l * 2]

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

            visited[dest][0] += 1
            visited[dest][1] = idx

            tmp.append(dest)

    return tmp

if N == K:
    print(0)
    print(1)

else:
    visited = [[0, 10000000] for i in range(100001)]
    visited[N][1] = 0

    t = 1
    q = [N]
    while visited[K][0] == 0:
        q = bfs(q, t)
        t += 1

    print(visited[K][1])
    print(visited[K][0])

3-3. C#

namespace boj_12851
{
    internal class Program
    {
        static int[,] visited;
        static List<int> tmp = new List<int>();

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();

            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]);

            visited = new int[100001, 2];

            for (int i = 0; i < 100001; i++)
                visited[i, 1] = int.MaxValue;

            visited[N, 0] = 1;
            visited[N, 1] = 0;

            int t = 1;
            int[] q = { N };

            while (visited[K, 0] == 0)
            {
                q = bfs(q, t);
                t++;
            }

            Console.WriteLine(visited[K, 1]);
            Console.WriteLine(visited[K, 0]);
        }

        static int[] bfs(int[] lst, int idx)
        {
            tmp.Clear();

            foreach (int l in lst)
            {
                int[] dests = { l + 1, l - 1, l * 2 };

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

                    if (visited[dest, 1] < idx)
                        continue;

                    visited[dest, 0]++;
                    visited[dest, 1] = idx;

                    tmp.Add(dest);
                }
            }

            return tmp.ToArray();
        }
    }
}