[알고리즘 문제 풀기] 숨바꼭질 3(13549)

1. 문제 풀이 아이디어

• BFS를 이용하여 목표 숫자 n에 도달할 때까지 최단 횟수를 탐색해 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int k = int.Parse(split[1]);
    bool[] visited = new bool[k + 100001];
    int count = 0;
    Queue<int> queue = new Queue<int>();
    visited[k] = true;
    queue.Enqueue(k);
    if (k != 0 && k % 2 == 0)
    {
        int temp = k;
        while (temp % 2 == 0)
        {
            temp /= 2;
            queue.Enqueue(temp);
            visited[temp] = true;
        }
    }
    while (queue.Count > 0)
    {
        int size = queue.Count;
        while (size > 0)
        {
            int cur = queue.Dequeue();
            if (cur == n)
            {
                sw.WriteLine(count);
                return;
            }
            if (cur > 0 && !visited[cur - 1])
            {
                visited[cur - 1] = true;
                queue.Enqueue(cur - 1);
                if ((cur - 1) != 0 && (cur - 1) % 2 == 0)
                {
                    int temp = cur - 1;
                    while (temp % 2 == 0)
                    {
                        temp /= 2;
                        if (visited[temp]) continue;
                        queue.Enqueue(temp);
                        visited[temp] = true;
                    }
                }
            }
            if (cur < visited.Length - 1 && !visited[cur + 1])
            {
                visited[cur + 1] = true;
                queue.Enqueue(cur + 1);
                if ((cur + 1) % 2 == 0)
                {
                    int temp = cur + 1;
                    while (temp % 2 == 0)
                    {
                        temp /= 2;
                        if (visited[temp]) continue;
                        queue.Enqueue(temp);
                        visited[temp] = true;
                    }
                }
            }
            size--;
        }
        count++;
    }
}

3. 정리

• 시작 숫자 k부터 시작하여 BFS 탐색을 진행한다.

• 현재 수가 짝수이면 나눌 수 있을 때까지 /2로 나눈 결과를 큐에 추가한다.

• 각 단계에서 현재 수가 n이면 그때의 count를 출력하고 종료한다.

• +1, 1 이동 후에도 해당 수가 짝수이면 /2로 반복 나누어 가능한 모든 경로를 탐색한다.

• 모든 수에 대해 방문 여부를 체크하여 중복을 방지하고 최소 이동 횟수를 찾는다.