미로 찾기

문제

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

 

입력

첫째 줄에 지도의 세로 길이 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

예제 출력

22

 

#코드

import sys
from collections import deque
 
 
def bfs():
  # start 좌표 : frame[n-1+1][1]  ==> [10][1]
  # end 좌표   : frame[1][m-1+1]  ==> [1][10] 
  
  # 1. 시작점을 큐에 삽입한다.
  # 2. 시작점을 색칠한다.
  # bfs 시작
  # 3. 큐에서 하나를 뺀다. 해당 값의 현재의 위치이다.
  # 4. 인접한 모든 정점에게 방문했는지 물어보고,
  #    방문을 하지 않았다면, 색칠하고 큐에 삽입한다.
  # 5. 모두 완료했다면 다시 3번으로 돌아간다.
  global frame
  
  visited = [[False]*(m+2) for _ in range((n+2))] # check[x] = True이면  [x]가 새칠됨
  deq = deque()
  deq.append((n-1+1, 1)) 
  visited[n-1+1][1] = True
  frame[n-1+1][1] = 0
  cnt = 0
  # 상, 하, 좌, 우
  dx = [0, 0, -1, 1]
  dy = [-1, 1, 0, 0] 
   
  while len(deq) > 0:
    x, y = deq.popleft()  
   
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if frame[nx][ny] > -1 and visited[nx][ny] == False:
        deq.append((nx, ny))
        frame[nx][ny] = frame[x][y] + 1
        visited[nx][ny] = True 
 
if __name__ == "__main__":
  n, m = map(int, sys.stdin.readline().split())
  frame = [[-1]*(m+2) for _ in range(n+2)]
  getInfo = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] 
  
  for i in range(n):
    for j in range(m):
      if getInfo[i][j] == 1:
        frame[i+1][j+1] = -1
      else:
        frame[i+1][j+1] = getInfo[i][j]  
    
  bfs()
  print(frame[1][m-1+1])

 

#복습

import sys
from collections import deque
 
def bfs(row, col):
  global matrix, visited, n, m
  
  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 matrix[nRow][nCol] == 0 and visited[nRow][nCol] == False:
        matrix[nRow][nCol] = matrix[popRow][popCol] + 1
        visited[nRow][nCol] = True
        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)] 
  visited = [[False]*m for _ in range(n)]
  
  bfs((n-1), 0)
   
  print(matrix[0][m-1])

 

# 복습

import sys 
from collections import deque
 
 
def BFS():
  global N, M, real_map
  # 상, 하, 좌, 우
  dy = [-1, 1, 0, 0]
  dx = [0, 0, -1, 1]
  
  deq = deque()
  deq.append((N, 1))
  
  while deq:
    yPos, xPos = deq.popleft()
    
    if yPos==1 and xPos==M:
      break
    
    for i in range(4):
      ny = dy[i]+yPos
      nx = dx[i]+xPos
      if real_map[ny][nx] == 0:
        real_map[ny][nx] = real_map[yPos][xPos]+1
        deq.append((ny, nx)) 
  print(real_map[1][M]) 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  N, M     = map(int, input().split())
  temp_map = [list(map(int, input().split())) for _ in range(N)]
  real_map = [[1]*(M+2) for _ in range(N+2)]
  
  for i in range(N):
    for j in range(M):
      real_map[i+1][j+1] = temp_map[i][j]
  
  BFS()