[bfs/백준] 2206번 : 벽 부수고 이동하기

- 문제: https://www.acmicpc.net/problem/2206

 

문제 이해 

- 0인 지점을 중심으로 bfs로 진행하다가 1을 만났을 때 한 번만 벽을 부숴서 진행할 수 있는 문제다.

- 벽을 1번만 뚫었는지 확인하기 위해 원소가 [0, 0]인 n x m 행렬을 이용한다.

0열에 값이 있으면 이전에 벽을 한번도 안 뚫은 경로이고, 1열에 값이 있으면 이전에 한 번 벽을 뚫은 경우이다. 

- 이전에 벽을 뚫었는지 여부를 일일히 visit[i][j][1] 값으로 확인해야돼서 케이스 나누는 게 복잡하다고 생각했는데 그게 아니라 

isCrash를 가지고 visit[i][j][isCrash]의 값으로만 진행하면 훨씬 간단해졌다.

 

풀이 로직

- n, m, matrix를 입력값으로 받는다.

- [0, 0]가 원소인 n x m 행렬 visit와 [i, j, isCrash] 원소를 추가하는 queue를 초기화한다.

- queue에서 x, y, isCrash를 얻은 다음, x == n - 1 and y == m - 1인 경우에 visit[x][y][isCrash]를 출력하고 while문을 탈출한다.

- x, y 위치에서 범위내의 상하좌우 값 중에 2가지 경우를 고려한 뒤 visit 값을 변경시키고, queue에 추가하면 된다.

1. 다음 노드의 값이 0이고, 아직 방문하지 않은 경우 : 이전에 벽을 뚫었건, 뚫지 않았건 상관없으므로 일반적인 bfs 적용하면 된다.

2. 다음 노드의 값이 1이고, isCrash == 0 인 경우 : 벽을 만났고, 이전에 벽을 부순적이 없다면 해당 벽을 부수고 이동할 수 있다. 

- 만약 while문에서 답을 출력하지 못했다면 답이 없는 경우이므로 -1을 출력한다. (상황은 flag 값으로 구분한다)

 

정답 풀이

from collections import deque

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input())))
    
visit = [[[0, 0] for _ in range(m)] for _ in range(n)]
visit[0][0][0] = 1
queue = deque()
queue.append([0, 0, 0])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
while queue:
    x, y, isCrash = queue.popleft()
    
    if x == n - 1 and y == m - 1:
        flag = True
        print(visit[x][y][isCrash])
        break
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == 0 and not visit[nx][ny][isCrash]:
                visit[nx][ny][isCrash] = visit[x][y][isCrash] + 1
                queue.append([nx, ny, isCrash])
            if matrix[nx][ny] == 1 and isCrash == 0:
                visit[nx][ny][isCrash + 1] = visit[x][y][isCrash] + 1
                queue.append([nx, ny, isCrash + 1])
     

if flag == False:
    print(-1)