[백준] 2178번: 미로 탐색 - python

미로 탐색

문제

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제

접근 방법

이 문제는 한 칸을 방문할 때마다 카운트 횟수를 세어 주면 된다.

• 큐에 미로의 위치와 카운트 횟수를 같이 저장하는 방법과
• 미로를 방문할 때마다 visited 혹은 graph 배열에 방문한 횟수를 저장하는 방법이 있다.

코드 1

from collections import deque

N, M = map(int, input().split())

graph = [list(input()) for _ in range(N)]

dx = (1,0,-1,0)
dy = (0,1,0,-1)

def check(x,y):
  return 0<=x<N and 0<=y<M

def bfs(start_x, start_y):
    q=deque()
    q.append((start_x, start_y, 1))
    visited = [[False]*M for _ in range(N)]
    visited[start_x][start_y] = True
    
    while q:
      x, y, cnt = q.popleft()
      if(x==N-1 and y==M-1) :
        return cnt
      
      for i in range(4):  
        mx = x + dx[i] 
        my = y + dy[i]
        if (check(mx, my) and graph[mx][my]=="1" and not visited[mx][my]):
          q.append((mx, my, cnt + 1))
          visited[mx][my] = True

print(bfs(0,0))

코드 2

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = []

for _ in range(n):
  graph.append(list(map(int, input().rstrip())))

def check(x, y):
  return 0<=x<n and 0<=y<m

def bfs(x, y):
  dx = [1,0,-1,0]
  dy = [0,1,0,-1]

  visited = [[False]*m for _ in range(n)]
  q = deque([(x, y)])
  visited[x][y] = True

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

    if x == n-1 and y == m-1:
      return visited[x][y]
    
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y

      if (check(nx, ny) and graph[nx][ny] and not visited[nx][ny]):
        visited[nx][ny] = visited[x][y] + 1
        q.append((nx, ny))

print(bfs(0,0))