[DFS] 미로찾기 - python

문제

입출력

💡 사고의 흐름

• dx, dy를 사용하여 주어진 x,y에서 갈 수 있는 지점을 파악해야 한다.
• 범위 내에 존재할 때, maze[x+dx][y+dy]가 0일 경우 갈 수 있도록 이동하고 check[x+dx][y+dy]값에 check[x][y]+1 를 기록해두어 check를 통해 거리를 count 할 수 있도록 한다!
• 이때, check[endX][endY] 의 값에 최종 거리가 기록되도록 하고 이를 출력하면 된다!

Code

import sys
from collections import deque
n,m = map(int, sys.stdin.readline().split())
maze =[]
check = [[0 for _ in range(1001)] for _ in range(1001)]
for i in range(n):
  maze.append(list(map(int, sys.stdin.readline().split())))

def dfs(startX,startY,endX,endY):
  q = deque()
  q.append((startX,startY))
  check[startX][startY]=0
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]
  
  while q:
    x,y= q.popleft()
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if nx>=0 and nx<n and ny>=0 and ny<m:
        if maze[nx][ny] == 0 and check[nx][ny]==0:
          q.append((nx,ny))
          check[nx][ny] = check[x][y]+1
          if nx == endX and ny==endY:
            break
  return check[endX][endY]

print(dfs(n-1,0,0,m-1))
  

2/9 다시 풀이

import sys
from collections import deque
n,m = map(int, sys.stdin.readline().split())
graph=[]
check = [[0 for _ in range(1001)] for _ in range(1001)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

if __name__=='__main__':
  for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
  bfs(n-1,0)
  print(check[0][m-1])