[알고리즘 문제 풀기] 벽 부수고 이동하기(2206)

1. 문제 풀이 아이디어

• 벽을 한 번까지 부술 수 있도록 방문 여부를 3차원 배열로 관리하여 BFS로 최단 경로를 찾아 문제를 해결한다.

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 m = int.Parse(split[1]);
    bool[,] map = new bool[n, m];
    for (int i = 0; i < n; i++)
    {
        string s = sr.ReadLine();
        for (int j = 0; j < m; j++)
        {
            if (s[j] == '1') map[i, j] = true;
        }
    }
    if (n == 1 && m == 1)
    {
        sw.WriteLine(1);
        return;
    }
    int[,] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    Queue<int[]> queue = new Queue<int[]>();
    queue.Enqueue(new int[] { 0, 0, 0 });
    bool[,,] visited = new bool[n, m, 2];
    visited[0, 0, 0] = true;
    int count = 1;
    bool fin = false;
    while (queue.Count > 0)
    {
        int size = queue.Count;
        count++;
        while (size > 0)
        {
            int[] cur = queue.Dequeue();

            for (int i = 0; i < 4; i++)
            {
                int nx = cur[0] + dir[i, 0];
                int ny = cur[1] + dir[i, 1];
                if (nx < 0 || n <= nx || ny < 0 || m <= ny || visited[nx, ny, 0] || (cur[2] == 1 && (visited[nx, ny, 1] || map[nx, ny]))) continue;
                if (nx == n - 1 && ny == m - 1)
                {
                    fin = true;
                    size = 0;
                    queue.Clear();
                    break;
                }
                int nb = map[nx, ny] ? 1 : cur[2];
                visited[nx, ny, nb] = true;
                queue.Enqueue(new int[] { nx, ny, nb });
            }
            size--;
        }
    }
    sw.WriteLine(fin ? count : -1);
}

3. 정리

• map 배열을 사용하여 벽의 위치를 저장한다.

• visited[n, m, 2] 배열을 사용하여 벽을 부순 상태(0 또는 1)를 포함해 방문 여부를 관리한다.

• BFS를 사용하여 최단 경로를 탐색하고, 한 번의 벽을 부술 수 있는 상태를 고려하여 이동을 진행한다.

• 목적지 (n-1, m-1)에 도달하면 현재까지의 이동 횟수를 출력하고 탐색을 종료한다.

• 목적지에 도달하지 못하면 -1을 출력하여 문제를 해결한다.