[백준][C#] 1697 숨바꼭질 - 실버1

문제 보기

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제                           

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

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

 

 

입력                          

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

 

출력                          

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

풀이방법                 

풀이에 들어가기 앞서,

이 문제를 풀면

13549 숨바꼭질3 - 골드5

문제도 날먹할 수 있다는 것을 알린다.

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

딱 한 부분만 바꾸면 되는데...

포스팅의 마지막 부분에서 서술하겠다.

(아마 정석 처리법과는 다를 수 있다. ㅋㅋ)

 

 

실버1 문제라기엔 참 쉽다.

문제를 그대로 BFS로 구현하기만 된다.

바로 BFS 코드로 넘어가자.

// key는 점, value는 해당 점까지 이동하는데 걸린 시간.
// dp로 풀이하려 했던 흔적으로, 딱히 dp와는 관련 없습니다.
// visited로 작명해도 괜찮을 것 같습니다.
Dictionary<int, int> dp = new Dictionary<int, int>();

int BFS()
{
	// 점들을 담을 queue 생성
    Queue<int> queue = new Queue<int>();

    // 수빈이의 현재 위치. 걸린 시간은 0.
    dp.Add(A, 0);
    queue.Enqueue(A);

    while (queue.Count > 0)
    {
        int num = queue.Dequeue();

		// 동생이 있을 수 있는 최대 위치보다 더 이동하게 되면 무시.
        if (num > 200000)
            continue;

		// 동생의 위치에 다다르면, 걸린 시간을 return한다.
        if (num == B)
        {
            return dp[num];
        }

		// 아래 3개의 if문은 수빈이가 이동할 수 있는 3개의 경우의 수.
        // Dictionary에 이미 현재 위치가 있으면 탐색 완료한 곳이니 또 볼 필요 없다.
        if (!dp.ContainsKey(num * 2) && num < B)
        {
        	// 현재 위치, 걸린 시간을 추가.
            dp.Add(num * 2, dp[num] + 1);
            queue.Enqueue(num * 2);
        }

        if (!dp.ContainsKey(num - 1))
        {
            dp.Add(num - 1, dp[num] + 1);
            queue.Enqueue(num - 1);
        }

        if (!dp.ContainsKey(num + 1))
        {
            dp.Add(num + 1, dp[num] + 1);
            queue.Enqueue(num + 1);
        }
    }

    return -1;
}

 

 

그럼 숨바꼭질 3 문제와 다른 점은?

 

순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

 

        if (!dp.ContainsKey(num * 2) && num < B)
        {
        	// 현재 위치, 걸린 시간을 추가.
            dp.Add(num * 2, dp[num]);
            queue.Enqueue(num * 2);
        }

 

전: dp.Add(num * 2, dp[num] + 1);

후: dp.Add(num * 2, dp[num]);

 

 

전체 코드

using System;
using System.Collections.Generic;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();
            int A = int.Parse(inputs[0]);
            int B = int.Parse(inputs[1]);

            Dictionary<int, int> dp = new Dictionary<int, int>();

            print.WriteLine(BFS());

            int BFS()
            {
                Queue<int> queue = new Queue<int>();
                
                dp.Add(A, 0);
                queue.Enqueue(A);

                while (queue.Count > 0)
                {
                    int num = queue.Dequeue();

                    if (num > 200000)
                        continue;

                    if (num == B)
                    {
                        return dp[num];
                    }

                    if (!dp.ContainsKey(num * 2) && num < B)
                    {
                        dp.Add(num * 2, dp[num] + 1);
                        queue.Enqueue(num * 2);
                    }

                    if (!dp.ContainsKey(num - 1))
                    {
                        dp.Add(num - 1, dp[num] + 1);
                        queue.Enqueue(num - 1);
                    }

                    if (!dp.ContainsKey(num + 1))
                    {
                        dp.Add(num + 1, dp[num] + 1);
                        queue.Enqueue(num + 1);
                    }
                }

                return -1;
            }

        }
    }
}