[Python : 나동빈] 미로 탈출

문제

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

• N * M 행렬 미로
• 1은 길, 0은 벽
• 1,1 지점부터 N, M 지점까지 이동하는데 필요한 최저횟수를 구하라.

# 입력 예시
5 6
101010
111111
000001
111111
111111

# 출력 예시
10

풀이

BFS에 익숙하지 않아 답안 코드를 많이 참고했다.
BFS에는 Queue가 사용되므로, Deque 를 이용하면 속도를 많이 줄일 수 있다.

• 1,1 지점은 0,0으로, N, M 지점은 N-1, M-1 지점으로 생각하면 된다.
• 처음 지점 좌표를 Queue에 삽입하고 큐가 빌 때까지 루프을 수행한다.
• 큐에서 좌표를 꺼내 상하좌우 값을 구한다.
• 상하좌우 각각에서 행렬을 벗어나거나 벽(0)일 경우,
  이미 방문한 곳(>1)일 경우 continue 시킨다.
• 방문한 적 없는 길(1)일 경우 해당지점에 지나온 지점수를 더한다.
• 해당지점 좌표를 Queue에 집어넣는다.
• 최종적으로 마지막지점(탈출구) 값을 반환한다.

from collections import deque

def bfs(miro, x, y, N, M):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or miro[nx][ny]!=1: continue

            miro[nx][ny] = miro[x][y]+1
            queue.append((nx, ny))
    
    return miro[N-1][M-1]

    
def solution():
    N, M = map(int, input().split())
    miro = []
    for i in range(N):
        miro.append(list(map(int, input())))
    
    print(bfs(miro, 0, 0, N, M))

solution()

DFS / BFS 는 연습할수록 재밌는 것 같다.
더 많이 풀어봐야겠다.