[BOJ 2178] 미로 탐색(Python)

문제링크

미로 탐색

풀이 전 계획 및 생각

각각의 수들이 붙어서 입력되기 때문에 입력이 조금 까다롭다고 생각했다.
입력만 제대로 처리하면, bfs를 이용해서 쉽게 해결할 수 있을 것이라고 생각했다.
bfs를 큐를 이용해서 풀었다.
최소의 이동 횟수를 구하는 분제였기 때문에, visited 배열을 이용해서 방문 여부 뿐만아니라 해당 칸까지 최소 몇 번만에 이동할 수 있는지를 저장했다.

풀이

import sys
from collections import deque
dr = [0,-1,0,1]
dc = [-1,0,1,0]

def bfs(graph,start_node,n,m):
    queue = deque([start_node])
    visited = [[0]*(m) for _ in range(n)]
    visited[0][0] = 1
    count = 1
    while queue:
        cur_node = queue.popleft()

        for i in range(4):
            next_r = cur_node[0]+dr[i]
            next_c = cur_node[1]+dc[i]
            if 0<=next_r<n and 0<=next_c<m and graph[next_r][next_c] == '1' and visited[next_r][next_c] == 0:
                queue.append([next_r, next_c])
                visited[next_r][next_c] = visited[cur_node[0]][cur_node[1]] + 1
    return visited[n-1][m-1]
n, m = map(int,sys.stdin.readline().split())
maze = [[] for _ in range(n+1)]
for i in range(n):
    string = sys.stdin.readline()
    for c in string:
        if c != '\n':
            maze[i].append(c)

print(bfs(maze,[0,0],n,m))

풀이하면서 막혔던 점과 고민했던 점

처음에는 dfs로 계산을 해보려고했는데, 특정 테스트 케이스에서는 맞지만 맞지않는 테스트 케이스도 있었다. 그래서 고민을 하다가 방문 여부와 해당 위치까지 올 수 있는 최소 이동횟수를 저장하는 방식으로 해결했다.

풀이 후 알게된 개념과 소감

상황에 맞게 visited 배열을 잘 바꾸고 저장하는 데이터도 바꿔주는게 좋다는 것을 배웠다.