미로 탐색 [백준 2178] - python

import sys
input = sys.stdin.readline
INF = 1e9

def BOJ2178() :
  global graph 
  global result 
  global N, M
  
  def dfs(x, y, count) :
    stack = []
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    result[x][y] = count 
    stack.append([x, y, count])

    while stack :
      curr_x, curr_y, curr_count = stack.pop()

      for dir_x, dir_y in directions :
        next_x = curr_x + dir_x 
        next_y = curr_y + dir_y
        next_count = curr_count + 1
        
        if 0 <= next_x < N and 0 <= next_y < M :
          if result[next_x][next_y] > next_count and graph[next_x][next_y] == '1':
            stack.append([next_x, next_y, next_count])
            result[next_x][next_y] = next_count

  N, M = map(int, input().split())
  graph = []
  result = [[INF for _ in range(M)] for _ in range(N)]
  for _ in range(N) :
    graph.append(list(input().rstrip()))
  
  dfs(0, 0, 1)
  print(result[N-1][M-1])

BOJ2178()

접근 방법 :

1. 그래프 탐색의 필요성을 느꼈고 최단 거리를 가져와야 하므로 모든 경우의 수를 탐색하는 bfs 보다는 dfs를 이용해야 겠다는 생각이 들었다.

2. 한번의 탐색시에 정답을 도출해 내고 싶어 최소의 칸 수에 대한 배열을 따로 설정, 탐색시마다 해당 배열의 값을 업데이트 시켜주고자 하였다. (result = 최소의 칸 수에 대한 배열)

3. result 배열의 default 값을 굉장히 큰 수로 선언후 dfs 탐색시에 기존의 값보다 큰 경우에만 stack에 추가 및 result의 값을 업데이트 해주었다. 

    result의 배열의 값이 비교값보다 작을 경우는 stack에 추가해주지 않아야 불필요한 업데이트 및 접근이 없을것으로 판단하였다. (목적없이 youtube를 보면서 시간을 낭비하는 것과 같은 개념이 아닐까??)

 

 

 

 

 

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

2178번: 미로 탐색