파이썬) 벽 부수고 이동하기 - BOJ

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())

arr = [list(map(int, input().rstrip())) for _ in range(n)]

visit = [[[0] * 2 for _ in range(m)] for _ in range(n)]


visit[0][0][0] = 1

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
q = deque()


q.append((0, 0, 0))

condition = False

while q:
    x, y, wall = q.popleft()

    if x == n-1 and y == m-1:
        condition = True
        print(visit[x][y][wall])
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny][wall] == 0:
            if arr[nx][ny] == 0:
                q.append((nx, ny, wall))
                visit[nx][ny][wall] = visit[x][y][wall] + 1

            if wall == 0 and arr[nx][ny] == 1:
                q.append((nx, ny, 1))
                visit[nx][ny][1] = visit[x][y][wall] + 1

for i in visit:
    print(i)
if not condition:
    print(-1)

 

처음엔 단순히 큐에 담는 wall이란 변수로 내가 한번도 부수지 않았으면 0, 한번이라도 부수었다면 1을 저장해

if arr[nx][ny] == 1 and wall == 0:

으로 벽을 부수고 이동했었다.

왜냐하면 경로상에 있는 벽을 부수고 이동하는 것이 "무조건" 경로가 짧아진다고 생각했었기 때문이다.

 

그러나 벽을 부수고 이동하는 것이 최단경로에서 좀 더 멀어진다는 생각을 하지 못했었다.

따라서 벽을 부수고 이동하는 경로와 벽을 부수고 이동하지 않는 경우 둘 모두를 계산해야했다.

결국 "벽을 안부스고 [n-1][m-1]에 이동한다 => 출력, 또는 벽을 부수고 이동하여 [n-1][m-1]에 도착했다 => 출력."으로 지금 경로가 최적의 경로라는 넓이 우선탐색에 맞는 알고리즘을 선택해야했다.

 

visit은 3차원 리스트로 x,y값과 wall값을 지정해주었다.

예를들어 x = 1, y = 2 일때 visit[x][y] 는 [0,0]이 된다. 여기서 visit[x][y][0] 은 벽을 안부수고 이동했을 때의 경로, visit[x][y][1]은 벽을 부수고 이동했을 때의 경로이다.

이후 while문을 돌며 bfs알고리즘을 반복적으로 실행해주면 된다.