[백준] 2206 - 벽 부수고 이동하기

1. 문제

2206번: 벽 부수고 이동하기

2. 개요

N x M 으로 표현되는 맵이 있다. 0은 이동 가능한 공간, 1은 벽으로 막힌 공간을 표현한다.

이동은 상하좌우로 한 칸씩만 가능하고 딱 한 번 벽을 부수고 지나갈 수 있다.

이 때 (1, 1)에서 (N, M)까지의 최소 거리를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

BFS를 이용한다.

그런데 벽을 한 번 부수고 지나갈 수 있기 때문에 벽을 부순 횟수를 항상 들고 있어야 한다.

visited로 벽을 부수지 않은 경우의 최단거리와 벽을 한번 부순 경우의 최단거리를 각각 표현한다.

visited[N-1, M-1]이 [0, 0]이 아니거나 큐가 먼저 빌 때까지 현 위치에서 상하좌우를 탐색한다.

맵 영역 밖이라면 continue, 이미 벽을 한 번 깼는데 또 벽을 만났다면 continue로 스킵한다.

두 조건을 통과한 후, 다음 이동할 공간이 벽을 만났다면 벽을 깬 카운트를 +1 하고 아니라면 그대로 진행한다.

visited[다음Y, 다음X, 다음 이동 시 벽을 깬 횟수]에 값이 이미 들어있다면 이미 더 빠른 길이 있었다는 얘기이므로 continue로 스킵한다.

값이 없다면 visited[다음Y, 다음X, 다음 이동 시 벽을 깬 횟수]를 visited[현재Y, 현재X, 현재까지 벽을 깬 횟수] + 1로 갱신한다.

[다음Y, 다음X, 다음 이동 시 벽을 깬 횟수]를 큐에 넣고 다시 반복한다.

while문을 탈출했다면 visited[N-1, M-1]이 [0, 0]인 경우 도달하지 못했으므로 -1을 출력하고,

그렇지 않다면 0이 아닌 값 중 작은 값을 답으로 출력한다.

3-2. Python

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

board = []
visited = [[[0, 0] for i in range(M)] for j in range(N)]

for i in range(N):
    board.append(list(map(int, sys.stdin.readline().rstrip())))

dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]
q = deque([[0, 0, 0]])
visited[0][0] = [1, 0]

while q and visited[N-1][M-1] == [0, 0]:
    now = q.popleft()
    nowY, nowX, nowbr = now[0], now[1], now[2]

    for i in range(4):
        nextY, nextX = nowY + dirY[i], nowX + dirX[i]

        if nextY < 0 or nextY >= N or nextX < 0 or nextX >= M:
            continue

        if (nowbr == 1 and board[nextY][nextX] == 1):
            continue

        if board[nextY][nextX] == 1:
            nextbr = nowbr + 1
        else:
            nextbr = nowbr

        if visited[nextY][nextX][nextbr]:
            continue

        visited[nextY][nextX][nextbr] = visited[nowY][nowX][nowbr] + 1

        q.append([nextY, nextX, nextbr])
        
answer = 100000000

for a in visited[N-1][M-1]:
    if a != 0 and answer > a:
        answer = a

print(answer) if answer != 100000000 else print(-1)

3-3. C#

internal class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);
        int answer = int.MaxValue;

        int[,,] visited = new int[N, M, 2];
        visited[0, 0, 0] = 1;

        int[,] board = new int[N, M];

        for (int i = 0; i < N; i++)
        {
            string row = Console.ReadLine();
            for (int j = 0; j < M; j++)
            {
                board[i, j] = int.Parse(row[j].ToString());
            }
        }

        int[] dirY = { -1, 0, 1, 0 };
        int[] dirX = { 0, -1, 0, 1 };
        Queue<int[]> q = new Queue<int[]>();

        q.Enqueue(new int[] { 0, 0, 0 });

        while (q.Count > 0 && visited[N - 1, M - 1, 0] == 0 && visited[N - 1, M - 1, 1] == 0)
        {
            int[] now = q.Dequeue();
            int nowY = now[0];
            int nowX = now[1];
            int nowbr = now[2];

            for (int i = 0; i < 4; i++)
            {
                int nextY = nowY + dirY[i];
                int nextX = nowX + dirX[i];

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue;

                if (nowbr == 1 && board[nextY, nextX] == 1)
                    continue;

                int nextbr;
                if (board[nextY, nextX] == 1)
                    nextbr = nowbr + 1;
                else
                    nextbr = nowbr;

                if (visited[nextY, nextX, nextbr] > 0)
                    continue;

                visited[nextY, nextX, nextbr] = visited[nowY, nowX, nowbr] + 1;

                q.Enqueue(new int[] { nextY, nextX, nextbr });
            }
        }

        for (int i = 0; i < 2; i++)
        {
            if (visited[N - 1, M - 1, i] != 0 && answer > visited[N - 1, M - 1, i])
                answer = visited[N - 1, M - 1, i];
        }

        answer = answer == int.MaxValue ? -1 : answer;

        Console.WriteLine(answer);
    }
}