[Python_DFS&BFS] 백준 2178번 : 미로 탐색

1. 문제

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

2178번: 미로 탐색

 

 

 

2. 풀이 과정

방법1) deque 라이브러리 활용하기

 

from collections import deque

n, m = map(int, input().split())
miro = [list(map(int, input())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#BFS => 최단 거리
def bfs(graph):
  q = deque()
  q.append((0, 0))
  
  while q:
    x, y = q.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m:
        if graph[nx][ny] == 1:
          graph[nx][ny] = graph[x][y]+1
          q.append((nx, ny))

  print(graph[n-1][m-1])

bfs(miro)

 

 

방법2) 리스트 자료형에 제공되는 메서드 이용

 

n, m = map(int, input().split())
miro = [list(map(int, input())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#BFS => 최단 거리
def bfs(graph):
  q = []
  q.append((0, 0))
  
  while q:
    x, y = q[0]
    x, y = q.pop(0)
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m:
        if graph[nx][ny] == 1:
          graph[nx][ny] = graph[x][y]+1
          q.append((nx, ny))

  print(graph[n-1][m-1])

bfs(miro)

 

 

방법3) 문자열로 받아와서 그대로 사용하기 - int로 바꾸는 연산 사용하지 않음

 

n, m = map(int, input().split())
miro = [list(input()) for _ in range(n)]
miro[0][0] = 1

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#BFS => 최단 거리
def bfs(graph):
  q = [(0, 0)]
  
  while q:
    x, y = q[0]
    x, y = q.pop(0)
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m:
        if graph[nx][ny] == '1':
          graph[nx][ny] = graph[x][y]+1
          q.append((nx, ny))

  print(graph[n-1][m-1])

bfs(miro)