[C#] 백준 1697번 문제풀이

문제번호: 1697

문제명: 숨바꼭질

문제링크: https://www.acmicpc.net/problem/1697

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 숨바꼭질 BFS문제를 풀었습니다. 수빈이가 동생을 잡기 위한 최소 비용을 출력해야합니다. 수빈이의 위치는 N이고 수빈이의 동생 위치는 K입니다. 움직일 수 있는 경우는 N+1, N-1, N x 2 입니다. BFS 내부에서 이미 방문하지 않았던 노드이고 범위를 초과하지 않았다면 N+1, N-1, N x 2 로 이동하도록 하였습니다.
다음은 정답코드입니다.

 

static void Main()
{
    using var sr = new StreamReader(Console.OpenStandardInput());
    using var sw = new StreamWriter(Console.OpenStandardOutput());

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

    int[] visited = new int[100001];
    Array.Fill(visited, - 1);

    Queue<int> queue = new Queue<int>();
    queue.Enqueue(N);
    visited[N] = 0;

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

        if (current == K)
        {
            sw.WriteLine(visited[current]);
            return;
        }

        int[] nexts = { current * 2, current + 1, current - 1 };
        foreach (var next in nexts)
        {
            if (next >= 0 && next <= 100000 && visited[next] == -1)
            {
                visited[next] = visited[current] + 1;
                queue.Enqueue(next);
            }
        }
    }
}