C# 백준 1261 알고스팟 (DFS + BFS)

 

1261번: 알고스팟

IDEA

9376번 탈옥 문제를 보다가 난 아직 준비가 덜 된 것 같아서 분류되어있는 더 쉬운 문제를 찾다 풀게 되었다. 다익스트라 알고리즘의 한 종류인데 특이하게 가중치가 0, 1 밖에 없다. '0-1 너비우선 탐색' 문제다. 이건 BFS로 해결할 수 있다. 정석적인 풀이를 찾아보려고 고수님들의 설명을 찾아보다 justicehui님의 깃허브 페이지에 있는 글을 발견했다. 요약하면 그래프 G에 V개의 정점, E개의 간선이 있고 가중치는 0, 1 뿐일 때 최단 경로를 찾는 알고리즘을 작성한다. 다익스트라 알고리즘으로 구현하는 것 보다 가중치가 0-1 뿐인 최단경로 문제에서 사용할 수 있는 0-1 BFS 알고리즘을 쓰는 것이 시간복잡도 면에서 더 이득이라는 것이다. 이 알고리즘은 Duque(덱)으로 구현한다. 그런데 C#에는 Deque이 없다.

자료 구조 자체를 제공하지 않으니 내가 이것부터 구현하기 전에는 연습조차 할 수 없는 상황이 벌어졌다. 어떡할까 고민하던 중 아이디어가 떠올랐다.

 

가중치가 0인 곳은 자유롭게 지나가도 상관이 없다. 그리고 0-1 BFS 알고리즘의 핵심은 이것이다.

1. 노드의 인접노드를 살핀다.

2. 가중치가 0이면 덱의 앞에 삽입한다.

3. 가중치가 1이면 덱의 뒤에 삽입한다.

 

"어 그러면 가중치가 0인 곳은 인접 노드와 비용 비교만 하고 지나간다는 건데

이거 DFS로 가중치 1 만날 때까지 탐색하면 되지 않나?"

 

그렇게 BFS안에 DFS를 집어넣는 코드를 작성했다.

 

CODE

using System;
using System.Collections.Generic;

public class Location
{
    public int x, y;
    public Location(int a, int b)
    {
        x = a; y = b;
    }
}

class Program
{
    static int N, M;
    static int[,] map = new int[100, 100];
    static int[,] weight = new int[100, 100];
    static bool[,] check = new bool[100, 100];
    static Queue<Location> BFS = new Queue<Location>();
    static void Main()
    {
        var nm = Console.ReadLine().Split();
        N = int.Parse(nm[1]); M = int.Parse(nm[0]);
        for(int i = 0; i < N; i++)
        {
            string row = Console.ReadLine();
            for (int j = 0; j < M; j++)
            {
                map[i, j] = row[j] == '0' ? 0 : 1;
                weight[i, j] = 10000;
            }
        }

        check[0, 0] = true;
        weight[0, 0] = 0;
        BFS.Enqueue(new Location(0, 0));
        while (BFS.Count > 0)
        {
            int a = BFS.Peek().x;
            int b = BFS.Peek().y;
            Search(a, b);
            BFS.Dequeue();
        }
        // 일단 겉으로는 BFS의 형태를 띈다.
        Console.WriteLine(weight[N - 1, M - 1]);
    }
    static void Search(int a, int b)
    {
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        int x, y;
        for(int i = 0; i < 4; i++)
        {
            x = a + dx[i]; y = b + dy[i];
            if (x < 0 || y < 0 || x >= N || y >= M) continue;
            // 상하 좌우의 인접노드가 주어진 범위 안에서 존재하는지 확인한다.

            if (!check[x, y])
            {
                if(map[x,y] == 0)
                // 빈칸인 경우 그냥 지나가도 된다.
                {
                    check[x, y] = true;
                    weight[x, y] = weight[a, b];
                    Search(x, y);
                    // 그래서 그냥 넘어간다.
                    // 이렇게 벽(1)을 만날 때까지 재귀하다가
                    // 벽을 만나면 BFS에 좌표를 넘긴다.
                }
                else
                // 빈칸이 아닌 경우 가중치 비교를 해줘야한다.
                {
                    check[x, y] = true;
                    weight[x, y] = Math.Min(weight[a, b] + 1, weight[x, y]);
                    BFS.Enqueue(new Location(x, y));
                    // 비교하고 다음 칸을 BFS에 넘겨준다.
                }
            }
        }
    }
}

결과는? 시간복잡도가 어떻게 되는 건지는 잘 모르겠다. 모든 노드 한번씩만 확인하니까 O(V)인가? 덱으로 구현한것과 비슷한걸까?