문제

문제 링크 : https://www.acmicpc.net/problem/2206

풀이

평범한 BFS 문제에 '벽을 한 개 까지 부수고 이동하여도 된다'라는 조건이 추가된 문제이다.

입력을 받고 상하좌우 dx,dy를 설정하는 부분까지는 평범한 BFS 풀이와 똑같다.

BFS를 구현하는 부분에서 차이가 있다.

우선 큐에 좌표와 거리 값 외에 벽을 부쉈는지의 정보도 넣어줘야 한다. 나는 벽을 부쉈으면 1을, 아니라면 0을 큐에 넣어줬다.

다음으로 visited 배열에 0,1 말고 2도 넣어주도록 했다. 왜냐하면 어느 칸을 갈 때 벽을 부수고 갈 수도 있고 부수지 않고 갈 수도 있기 때문에 두 경우를 구분해줘야하기 때문이다. 벽을 부수지 않고 도달했다면 2를, 벽을 부수고 도달했다면 1을 넣어줬다. visited[nx][ny]가 2일 때는 continue를 해주고, visited[nx][ny]가 1일 때는 (nx,ny)까지 벽을 부수지 않고 온 경우에 한해서 큐에 nx,ny를 넣어주었다. 그렇지 않다면 continue를 해주었다.

이후엔 (nx,ny)까지의 거리들 중 가장 짧은 거리를 출력하도록 했다.

import sys
from collections import deque
input = sys.stdin.readline

n,m=map(int,input().split())
l = [0 for i in range(n)]

for i in range(n):
    l[i] = list(map(int,list(input().rstrip())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]


if n == m == 1:
    result = 1
else:
    queue = deque()
    queue.append((0,0,1,0))
    visited = [[0 for i in range(m)] for j in range(n)]
    visited[0][0] = 1
    result = -1
    while queue:
        x,y,leng,wall = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nwall = wall
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if visited[nx][ny] != 0:
                if visited[nx][ny] == 2:
                    continue
                if visited[nx][ny] == 1 and nwall == 1:
                    continue
            if l[nx][ny] == 1:
                if wall == 1:
                    continue
                else:
                    nwall = 1
            else:
                if nwall == 1:
                    visited[nx][ny] = 1
                else:
                    visited[nx][ny] = 2
            if result == -1:
                if nx == n - 1 and ny == m - 1:
                    result = leng + 1
            else:
                if nx == n - 1 and ny == m - 1:
                    if result > leng + 1:
                        result = leng + 1
            queue.append((nx,ny,leng+1,nwall))


print(result)