[백준] 2178번 미로 탐색 파이썬 해설

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

2178번: 미로 탐색

BFS로 분류된 문제이다.

BFS를 풀어본 적이 있다면 해당 문제의 코드를 조금만 변형하면 문제를 풀 수 있을 것이다.

 

풀이

---

BFS알고리즘의 기본적인 방법으로 문제에 접근했다.

from collections import deque
import sys
input = sys.stdin.readline

find_arr = [(-1, 0), (0, -1), (0, 1), (1, 0)]

먼저 문제의 규칙을 적용할 수 있는 리스트를 선언한다.

현재 위치에서 인접한 곳만 갈 수 있다는 조건이 있으므로 상, 하, 좌, 우 만 고려하면 된다.

알고리즘 문제를 파이썬으로 풀 때는 최적화된 모듈을 최대한 사용하는 게 좋기 때문에 deque를 사용했다.

 

if __name__ == "__main__":
    N, M = map(int,input().split())
    arr = [[False for i in range(M)] for i in range(N)]

    for i in range(N):
        for j, v in enumerate(input().rstrip()):
            if int(v):
                arr[i][j] = True
    print(solution(arr, N-1, M-1))

각각의 수들이 붙어서 입력되는 문제이다.

먼저 문제에서 요구하는 크기의 리스트를 선언하며 모든 원소를 False로 초기화한다.

이동이 가능한 점이 입력되면 해당 점을  True로 변경해주었다.

 

def solution(arr, N, M):
    #(0, 0)에서 출발한다.
    #(N, M)에서 멈춘다.
    visit = [[0 for i in range(M+1)] for i in range(N+1)]
    q = deque()
    q.append([0,0])
    visit[0][0] = 1
    while q:
        now_x, now_y = q.popleft()
        if now_x == N and now_y == M: break
        for i, j in find_arr:
            next_x = now_x + i
            next_y = now_y + j

            if not (0 <= next_x <= N and 0 <= next_y <= M): continue
            if visit[next_x][next_y] : continue
            if not arr[next_x][next_y] : continue

            visit[next_x][next_y] = visit[now_x][now_y] + 1
            q.append([next_x, next_y])

    return visit[N][M]

풀기 쉽게 (0, 0)에서 출발하여 (N, M)로 가는 BFS를 구하는 함수를 구현했다.

방문했던 곳에 또 방문하는 경우를 배제하기 위해 방문 점을 확인하는 리스트 visit을 선언해준다.

 

dequeue가 emty상태가 될 때까지 while문을 반복하며 시작점을 기준으로 BFS(너비 우선 탐색)을 진행한다. 

dequeue를 leftpop을 한 점을 기준으로 조건에 해당하는 상, 하, 좌, 우 점을 탐색(방문)하게 된다.

조건은 세 가지로 나눴다.

1. 배열의 인덱스를 초과하지 않는가

2. 이미 방문했던 점 인가

3. 이동할 수 있는 점 인가 (테스트 케이스의 입력 중 1인가를 확인)

 

세 조건에 모두 해당한다면 dequeu에 삽입하는 과정을 네 번 반복 후 while문의 상단으로 돌아가 같은 과정을 반복한다.

 

결과

---

이번 문제는 한 번의 시도만에 맞아서 괜히 기분이 좋아지는 문제였다. ㅎㅎ

블로그를 운영한 지 얼마 되지 않아서 나만의 프레임이 없다.

매번 새로운 프레임으로 예쁘게 정리해보려고 노력 중이다.