C# 백준 13913 숨바꼭질 4 (너비우선탐색)

1697번: 숨바꼭질

숨바꼭질 1번부터 시작해야겠다. 모든 정점 V가 범위 내의 정점 V + 1, V - 1, V * 2 와 연결되어있고 가중치는 1이다. BFS로 탐색을 시작해서 찾는대로 시간을 출력하게 하면 될 것 같다.

using System;
using System.Collections.Generic;
class Program
{
    static int n, k;
    static int[] time = new int[100001];
    static bool[] check = new bool[100001];
    static Queue<int> BFS = new Queue<int>();
    static void Main()
    {
        var nk = Console.ReadLine().Split();
        n = int.Parse(nk[0]);
        k = int.Parse(nk[1]);
        BFS.Enqueue(n);
        time[n] = 0;
        check[n] = true;
        while (BFS.Count > 0)
        {
            if (BFS.Peek() == k)
            {
                Console.WriteLine(time[k]);
                break;
            }
            
            // 같은 구조의 코드가 3번 반복되고있다.
            // 탐색할 곳 까지의 변위를 배열로 저장해서 반복하면 줄일 수 있다.
            if (BFS.Peek() > 0)
            {
                if (!check[BFS.Peek() - 1])
                {
                    time[BFS.Peek() - 1] = time[BFS.Peek()] + 1;
                    BFS.Enqueue(BFS.Peek() - 1);
                    check[BFS.Peek() - 1] = true;
                }
            }
            if (BFS.Peek() < 100000)
            {
                if (!check[BFS.Peek() + 1])
                {
                    time[BFS.Peek() + 1] = time[BFS.Peek()] + 1;
                    BFS.Enqueue(BFS.Peek() + 1);
                    check[BFS.Peek() + 1] = true;
                }
            }
            if (BFS.Peek() * 2 <= 100000)
            {
                if (!check[BFS.Peek() * 2])
                {
                    time[BFS.Peek() * 2] = time[BFS.Peek()] + 1;
                    BFS.Enqueue(BFS.Peek() * 2);
                    check[BFS.Peek() * 2] = true;
                }
            }
            BFS.Dequeue();
        }
    }
}

 

그럼 이제 다음 문제로 넘어가보자.

 

 

12851번: 숨바꼭질 2

이번에는 중복되는 경우를 모두 탐색해줘야한다. 그러니까 한 계층 안에있는 BFS를 모두 탐색해서 그 안에 찾는 결과가 몇개나 있는지를 확인해야한다. 이걸 위해서는 탐색한 지점에 대한 재 탐색을 어떻게할지 고민해야한다. 그냥 무작정 "갔어도 또 가!" 해버렸다간 탐색 범위 조금만 넓어지면 StackOverFlowException이 발생한다. OutOfMemoryException이 발생하거나. 여기는 동적계획법이 조금 첨가되면 좋을 것 같다.

 

1. 만약 새로 탐색한 지점이 방문한적이 없는 곳이라면? 무조건 이번 방문이 최단거리다. 바로 시간 + 1해서 저장하고 현재 탐색 경우의 수를 넘겨준다.

2. 만약 방문한 적이 있는 곳이라면? 시간을 비교해보자. 세 가지 경우를 생각해보자. 현재 시간 + 1보다 작은 경우, 같은 경우, 큰 경우.

2-1. 작은 경우 이미 여긴 더 빠른 경로가 있다는 것이다. 패스. 다음 탐색을 시도하지 않아도 된다.

2-2. 같은 경우 여기 다른 방법, 같은 비용으로 탐색한 경우의 수가 저장되어 있을 것이다. 현재 탐색 경우의 수를 합쳐서 저장해준다. 그리고 이미 다른 탐색에서 다음 탐색을 큐에 삽입했을 것이기 때문에 패스.

2-3. 큰 경우. BFS에서 이런 경우는 없다. 탐색 비용은 점점 늘어가는데 나보다 먼저 탐색한 녀석이 나보다 많은 비용을 탐색을 했을리가 없다. 이건 그냥 고려하지 않는다.

3. 다음 탐색을 실시한다. 만약 다음 탐색의 저장된 시간이 탐색 목표의 시간보다 더 커졌다면 그만해도 된다. 다음 계층으로 내려와버렸다는 뜻이다. 더 탐색해도 목표 계층에는 아무런 변화가 없다.

 

그럼 최초의 정점에는 탐색 경우의 수를 1로 저장해주면 된다. 입력을 3 7로 하는 경우를 적어보자. 탐색 순서는 -1, +1, *2로 한다.

현재 위치	3	2	4	6	1	3	4	3	5
시간	0	1	1	1	2	패스	패스	패스	2
경우의 수	1	1	1	1	1				1

8	5	7	12	0
2	2	2	2	3	시간이 3초가 됐다. 가장 빨리 7에 도착하는 시간은 2초다.
1	2	1	1	1	여기부터는 탐색을 실시하지 않아도 된다.

특별한 경우의 시간을 확실히 줄여줄 수 있는 방법이 있다. 목표 지점을 넘어서 탐색을 시작하는 경우, 목표 지점에서 출발하는 경우. 전자는 경우의 수가 1가지 뿐이며 걸리는 시간은 거리와 같다. 후자도 경우의 수가 1가지 뿐이고 걸리는 시간은 0이다.

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static int N, K, S;
    static int[] count = new int[100002];
    static int[] time = Enumerable.Repeat(-1, 100002).ToArray<int>();
    static Queue<int> BFS = new Queue<int>();
    static void Main()
    {
        var nk = Console.ReadLine().Split();
        N = int.Parse(nk[0]);K = int.Parse(nk[1])
        ;
        // 앞서 말한 2가지 경우를 따로 제외시켰다.
        // 이후에 범위를 탐색 범위를 좁히기 위해서다.
        // BFS는 탐색 범위를 좁혀주면 시간 효율이 높아진다.
        if (N == K) Console.WriteLine("0\n1");
        else if (N > K) Console.WriteLine($"{N - K}\n1");
        else
        {
            BFS.Enqueue(N);
            time[N] = 0;
            count[N] = 1;
            while (BFS.Count > 0)
            {
                S = BFS.Dequeue();
                int[] d = { -1, 1, S };                             // -1, +1, *2
                for (int i = 0; i < 3; i++)
                {
                    if (S + d[i] < 0 || S + d[i] > K + 1) continue; // 생각 안해도 되는 경우들 0 미만의 index,
                                                                    // K를 넘어가버리면 무조건 시간 손해
                    if (time[S + d[i]] != -1)                       // 왔던 곳이면
                        if (time[S] + 1 == time[S + d[i]]) count[S + d[i]] += count[S]; else { }
                                                                    // 시간 같으면 가짓수 더해주기
                    else
                    {                                               // 처음 왔으면
                        time[S + d[i]] = time[S] + 1;               // 시간 더해주기
                        count[S + d[i]] = count[S];                 // 가짓수 가져오기
                        BFS.Enqueue(S + d[i]);                      // 큐에 추가
                    }                                               // 왔던 곳은 큐에 추가 안하기 때문에
                }                                                   // K에 처음 도착할 때만 K 이후를 탐색하고
            }                                                       // 탐색 끝남
            Console.WriteLine(time[K]);
            Console.WriteLine(count[K]);
        }
    }
}

 

3번째 숨바꼭질이다. 이번에는 순간이동에 걸리는 시간이 0이 되었다. 모든 가중치가 1이었던 다익스트라 문제에서 가중치가 0 또는 1인 0-1 BFS 문제가 되었다. 그런데 이 문제는 숨바꼭질 4를 푸는데 영향이 없기 때문에 다음에 따로 정리하겠다. 4번이다.

13913번: 숨바꼭질 4

 

IDEA

스페셜 저지이기 때문에 복수 정답이 인정된다. 경우의 수를 따지지 않아도 된다. 이 문제는 경로를 기억해야한다. 처음 떠올린 생각은 string을 이용해 경로를 저장하는 것이었다. 새로운 정점을 찾을 때마다 이전 정점에 기록된 경로를 불러와 현 탐색을 덧붙이는 방식이다. 당연히 메모리 초과가 떴다. 수만개의 문자열을 만들고 합치고 새로 저장하니 매 탐색마다 새롭게 2개의 문자열이 만들어졌다. 두번째 방법은 StringBuilder 구조체였다. 배열로 선언하려고 했더니 컴파일 에러가 발생했다. List를 선언하고 List안에 StringBuilder구조체를 저장하기로 했다. 좀 더 나아질까 했지만 역시나 새롭게 S경로를 저장할 때 문자열이 하나 생성되고 그걸 다시 StringBuilder에 저장하는 방식이라 메모리 상 개선점이 전혀 없었다. 다음으로 생각한 방법은 Queue였다. List를 선언하고 그 안에 Queue를 저장해 새로운 정점을 탐색하면 Queue를 넘겨주고 다음 경로를 삽입하는 방식이었다. 효과적일 것 같았지만 역시나 메모리 초과가 떴다. 전부 다 실패했지만 List<Queue>라는 새로운 컬렉션 안에 컬렉션 넣기를 구현해낸 성과는 있었다...

다른 사람들의 해설을 찾아봤다. 새로운 배열을 만들고 매 탐색마다 이전 정점의 위치를 기록하는 방법이 있었다. 이렇게 하면 매 탐색마다 중복되는 메모리 손실이 없고 경로를 복사하는 시간 손실도 없다. 탐색을 끝내고 나면 Stack을 이용해 경로를 역탐색해서 출발 정점으로 돌아가고 Stack에 저장된 값들을 하나씩 출력해내면 된다.

 

CODE

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
class Program
{
    static int N, K, S;
    static int[] time = Enumerable.Repeat(-1, 100002).ToArray<int>();
    static int[] from = new int[1000001];
    static Queue<int> BFS = new Queue<int>();
    static Stack<int> path = new Stack<int>();
    static StringBuilder Path = new StringBuilder();
    static void Main()
    {
        var nk = Console.ReadLine().Split();
        N = int.Parse(nk[0]); K = int.Parse(nk[1]);
        if (N >= K)  // 거꾸로 가는 케이스 제거
        {
            Console.WriteLine(N == K ? 0 : N - K);
            if (N == K) Console.WriteLine(N);
            else
            {
                for (int i = N; i > K; i--)
                {
                    Console.Write(i + " ");
                }
                Console.Write(K + "\n");
            }
            return;
        }
        else
        {
            BFS.Enqueue(N);
            time[N] = 0;
            while (BFS.Count > 0)
            {
                S = BFS.Dequeue();
                if (S == K) break;
                int[] d = { -1, 1, S };
                for (int i = 0; i < 3; i++)
                {
                    if (S + d[i] < 0 || S + d[i] > K + 1) continue;
                    if (time[S + d[i]] == -1)
                    {
                        BFS.Enqueue(S + d[i]);
                        time[S + d[i]] = time[S] + 1;
                        from[S + d[i]] = S;	// 이전 정점의 정보를 저장한다.
                    }
                }
            }
            Console.WriteLine(time[K]);
            S = from[K];
            for (int i = 0; i < time[K]; i++)	// Stack으로 역탐색
            {
                path.Push(S);
                S = from[S];
            }
            while(path.Count > 0)				// Stack에서 꺼내기
            {
                Path.Append(path.Pop() + " ");
            }
            Path.Append(K);
            Console.WriteLine(Path);
        }
    }
}