목수의 미로 탈출

문제

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 찾으려 한다. 그런데 목수는 도끼 하나를 갖고 있으며, 이 도끼를 이용하여 벽을 깨부술 수 있다. 하지만 이 도끼는 내구성이 그렇게 좋지 않기 때문에, 벽을 최대 1개밖에 깰 수 없다. 목수가 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 물론, 벽은 최대 1개까지 깰 수 있다. 아래 예제의 경우 ‘X’ 로 표시된 벽을 깰 경우 거리 18만에 출발점에서 도착점으로 이동할 수 있다.

 

입력

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

 

출력

목수가 (N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다. 목수는 미로를 항상 탈출할 수 있다고 가정한다.

 

예제 입력

10 10

0 0 0 0 0 0 1 1 0 0

0 1 1 1 0 0 1 0 1 0

0 1 1 1 0 0 1 0 1 0

0 0 0 0 0 0 0 0 1 0

0 0 1 1 1 1 0 0 1 0

0 0 0 0 0 0 1 1 0 0

0 0 1 1 1 0 1 1 0 0

0 0 1 1 1 0 0 0 0 0

0 0 0 0 0 1 1 1 0 0

0 0 0 0 0 0 0 1 0 0

예제 출력

18

 

예제 입력

10 10

0 0 0 0 0 0 1 1 0 0

0 1 1 1 0 0 1 1 1 0

0 1 1 1 0 0 1 1 1 0

0 0 0 0 0 0 0 1 1 0

0 0 1 1 1 1 0 1 1 0

0 0 0 0 0 0 1 1 0 0

0 0 1 1 1 0 1 1 0 0

0 0 1 1 1 0 0 1 0 0

0 0 0 0 0 1 1 1 1 1

0 0 0 0 0 0 0 1 0 0

예제 출력

22

 

 

 

#코드

import sys
from collections import deque
 
def getResult(y, x, cost):
  
  deq = deque()
  deq.append((y, x))
  visited[y][x] = True
  
  dy = [-1, 1, 0, 0]
  dx = [0, 0, -1, 1]
  
  while len(deq) > 0:
    popY, popX = deq.popleft()
    for i in range(4):
      ny = popY + dy[i]
      nx = popX + dx[i]
      if 0 <= ny and ny < n and 0 <= nx and nx < m and visited[ny][nx] == False:
        visited[ny][nx] = True
        cost[ny][nx] = cost[popY][popX] + 1
        if matrix[ny][nx] == 0:
          deq.append((ny, nx))
  
  return cost
  
 
if __name__ == "__main__":
  n, m    = map(int, sys.stdin.readline().split())
  matrix  = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
  c1, c2 = [[0]*m for _ in range(n)], [[0]*m for _ in range(n)]
  visited = [[False]*m for _ in range(n)]
 
  c1 = getResult(n-1, 0, c1) 
  visited = [[False]*m for _ in range(n)]
  c2 = getResult(0, m-1, c2) 
  
  result = 987987987
  for i in range(n):
    for j in range(m):
      if matrix[i][j] != 0 and c1[i][j] > 0 and c2[i][j] > 0:
        if result > c1[i][j] + c2[i][j]:
          result = c1[i][j] + c2[i][j]
  print(result)

 

#구현 (복습) : 처음보다 훨씬 수월하다 

import sys
from collections import deque
 
def bfs(row, col, cost):
  global matrix, visited
  visited[row][col] = True
  
  # 상, 하, 좌, 우
  dy = [-1, 1, 0, 0]
  dx = [0, 0, -1, 1]
  
  deq = deque()
  deq.append((row, col))
  
  while len(deq) > 0:
    popRow, popCol = deq.popleft()
    for i in range(4):
      nRow = popRow + dy[i]
      nCol = popCol + dx[i]
      
      if 0 <= nRow and nRow < n and 0 <= nCol and nCol < m and visited[nRow][nCol] == False:
        cost[nRow][nCol]    = cost[popRow][popCol] + 1
        visited[nRow][nCol] = True
        if matrix[nRow][nCol] == 0:
          deq.append((nRow, nCol))
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n, m    = map(int, input().split())
  matrix  = [list(map(int, input().split())) for _ in range(n)] 
  c1, c2  = [[0]*m for _ in range(n)], [[0]*m for _ in range(n)]
  visited = [[False]*m for _ in range(n)]
  
  bfs((n-1), 0, c1)
  visited = [[False]*m for _ in range(n)]
  bfs(0, (m-1), c2) 
  
  result = 1e9 
  for row in range(n):
    for col in range(m):
      if matrix[row][col] != 0 and c1[row][col] > 0 and c2[row][col] > 0:
        temp = c1[row][col] + c2[row][col]
        if result > temp:
          result = temp
          matrix[row][col] = temp
        
        
  print(result)  

 

# 복습

import sys
from collections import deque
 
def BFS(row, col, cost):
  global matrix, visited, n, m
  
  # 상,하,좌,우
  dy = [-1, 1, 0, 0]
  dx = [0, 0, -1, 1]
  
  deq=deque()
  deq.append((row, col))
  visited = [[False]*m for _ in range(n)]
  
  while deq:
    popRow, popCol = deq.popleft()
    for i in range(4):
      nRow=popRow+dy[i]
      nCol=popCol+dx[i]
      
      if 0<=nRow<n and 0<=nCol<m and not visited[nRow][nCol]:
        cost[nRow][nCol]    = cost[popRow][popCol]+1
        visited[nRow][nCol] = True
        if matrix[nRow][nCol]==0:
          deq.append((nRow, nCol))
    
  
    
 
if __name__ == "__main__":
  input=sys.stdin.readline
  
  n, m    = map(int, input().split())
  matrix  = [list(map(int, input().split())) for _ in range(n)]
  c1, c2  = [[0]*m for _ in range(n)], [[0]*m for _ in range(n)]
  
  
  BFS((n-1), 0, c1)
  BFS(0, (m-1), c2)
  
  result = int(1e9)
  for row in range(n):
    for col in range(m):
      if matrix[row][col]!=0 and c1[row][col]>0 and c2[row][col]>0:
        temp = c1[row][col]+c2[row][col]
        if result>temp:
          result = temp
  print(result)