[Baekjoon Online Judge] 백준 2178번 미로 탐색(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2178번 미로 탐색

(Python)

(글쓴날 : 2020.03.30)

 

---

* Baekjoon Online Judge, 백준 2178번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2178번 미로 탐색

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

2) 풀이 과정

N, M이 주어지고, 0과 1이 저장되어 있는 N X M 크기의 2차원 배열이 주어질 때, 0을 이동할 수 없는 칸, 1을 이동할 수 있는 칸으로 가정하여 [0,0]에서 [N-1, M-1]까지 이동시키는 최소 횟수를 출력하는 문제입니다.

단, 이동이 불가능한 경우는 없으며 최종 칸에 도착한 경우도 이동한 횟수로 포함합니다.

 

저의 경우, BFS를 적용해 문제에 접근했으며, 코드상에 굳이 BFS() 함수를 생성하진 않았지만 큐를 이용해 2차원 배열을 완전 탐색하여 최소 이동 횟수를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
maze = [list(map(int, input().rstrip())) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
dx, dy = [1, -1, 0, 0], [0, 0, -1, 1]
dq = deque()
 
dq.append((0, 0, 0))
 
while len(dq):
    i, j, moveCount = dq.popleft()
    
    if i == N - 1 and j == M - 1:
        print(moveCount + 1)
        exit()
 
    if not visit[i][j]:
        visit[i][j] = True
 
        for way in range(4):
            ii, jj = i + dx[way], j + dy[way]
 
            if ii < 0 or ii > N - 1 or jj < 0 or jj > M - 1:
                continue
 
            if maze[ii][jj] == 0:
                continue
 
            dq.append((ii, jj, moveCount + 1))

---