[ BOJ/C# ] 1697 숨바꼭질

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

1697번: 숨바꼭질

BFS 문제이다. 

많이 접해오던 BFS 문제와는 다르게 2차원배열로 이루어지지 않았다. 

문제에서 주어진 3가지의 경우로 최소 시간을 구해야 한다. 

x-1, x+1, x*2의 가능 조건들을 설정한다. 

주의해야 할 점은, x*2의 값이 K+1일 경우 x-1로 K를 만들어주는 경우도 있기 때문에 범위를 K+1로 설정해주어야 한다. 

이 부분을 간과하여 처음에 틀렸다. 

using System;
using System.IO;

namespace B1697
{
    class Program
    {
        static int N, K;
        static Queue<(int, int)> q = new Queue<(int, int)>();
        static bool[] visited = new bool[100001];
        static int Min = 0;

        static void BFS()
        {
            q.Enqueue((N, 0));
            visited[N] = true;
            while(q.Count > 0)
            {
                var deq = q.Dequeue();
                int deqx = deq.Item1;
                int time = deq.Item2;
                //목표에 도달했다면 Min과 비교
                if (deqx == K)
                {
                    if (Min == 0) Min = time;   //Min에 저장된 값이 없다면 새로 저장
                    else if (Min > time) Min = time;    //Min보다 작다면 저장
                }
                //경우의 수들 q에 저장
                if (deqx + 1 <= K && visited[deqx + 1] == false)
                {
                    q.Enqueue((deqx + 1, time + 1));
                    visited[deqx + 1] = true;
                }
                if (deqx - 1 >= 0 && visited[deqx - 1] == false)
                {
                    q.Enqueue((deqx - 1, time + 1));
                    visited[deqx - 1] = true;
                }
                if (deqx * 2 <= K + 1 && visited[deqx * 2] == false)
                {
                    q.Enqueue((deqx * 2, time + 1));
                    visited[deqx * 2] = true;
                }
            }
        }
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int[] nk = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            N = nk[0];
            K = nk[1];

            BFS();
            sw.Write(Min);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}