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

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

BFS와 우선순위 큐를 이용하여 해결한 문제이다. 먼저 벽을 부순 경우(d1)와 부수지 않은 경우(d0)를 나누어 현재 가려고 하는 지점에 최소 이동 비용을 저장하였다. 벽을 부순 경우는 d0에서 최소 비용을 고려하 이동하였다. 벽을 부수지 않은 경우 1을 만나면 d1에서 최소 비용을 고려하여 이동하였다. 벽을 부수지 않은채로 0을 만나면 d0에서 최소 비용을 고려하여 이동하였다. 그리고 우선순위 큐를 사용했으니 d1의 마지막과 d0의 마지막을 한번씩 방문했던게 확실하면 그 자리에서 종료하고 둘 중에 작은 값을 출력하였다. 둘 다 방문한 흔적이 없으면 -1을 출력하였다.

import sys
import heapq

field = []

NOT_VISIT = 987654321

N, M = map(int, sys.stdin.readline().split())
d0 = [[NOT_VISIT for i in range(M)] for i in range(N)]
d1 = [[NOT_VISIT for i in range(M)] for i in range(N)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(N):
  temp = list(map(int, sys.stdin.readline().rstrip('\n')))
  field.append(temp)

def bfs():
  pq = []

  heapq.heappush(pq, (1, [0, 0, 0]))
  d0[0][0] = 1
  d1[0][0] = 1

  while len(pq) != 0:
    front = heapq.heappop(pq)
    x = front[1][0]
    y = front[1][1]
    destroy = front[1][2]
    if d0[N - 1][M - 1] != NOT_VISIT and d1[N - 1][M - 1] != NOT_VISIT:
      break
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < N and 0 <= ny < M :
        if field[nx][ny] == 1:
          if destroy == 0:
            if d1[nx][ny] > d0[x][y] + 1:
              d1[nx][ny] = d0[x][y] + 1
              heapq.heappush(pq, (d1[nx][ny], (nx, ny, 1)))
        else:
          if destroy == 0:
            if d0[nx][ny] > d0[x][y] + 1:
              d0[nx][ny] = d0[x][y] + 1
              heapq.heappush(pq, (d0[nx][ny], (nx, ny, 0)))
          else:
            if d1[nx][ny] > d1[x][y] + 1:
              d1[nx][ny] = d1[x][y] + 1
              heapq.heappush(pq, (d1[nx][ny], (nx, ny, 1)))

bfs()
if d0[N - 1][M - 1] == NOT_VISIT and d1[N - 1][M - 1] == NOT_VISIT:
  sys.stdout.write(str(-1) + '\n')
elif d0[N - 1][M - 1] < d1[N - 1][M - 1]:
  sys.stdout.write(str(d0[N - 1][M - 1]) + '\n')
else:
  sys.stdout.write(str(d1[N - 1][M - 1]) + '\n')