[Baekjoon Online Judge] 백준 2178번 미로 탐색
(Python)
(글쓴날 : 2020.03.30)
* Baekjoon Online Judge, 백준 2178번 문제 Python 언어 풀이입니다.
* 소스 코드의 저작권은 글쓴이에게 있습니다.
백준 2178번 미로 탐색
1) 문제
문제 링크 : https://www.acmicpc.net/problem/2178
2) 풀이 과정
N, M이 주어지고, 0과 1이 저장되어 있는 N X M 크기의 2차원 배열이 주어질 때, 0을 이동할 수 없는 칸, 1을 이동할 수 있는 칸으로 가정하여 [0,0]에서 [N-1, M-1]까지 이동시키는 최소 횟수를 출력하는 문제입니다.
단, 이동이 불가능한 경우는 없으며 최종 칸에 도착한 경우도 이동한 횟수로 포함합니다.
저의 경우, BFS를 적용해 문제에 접근했으며, 코드상에 굳이 BFS() 함수를 생성하진 않았지만 큐를 이용해 2차원 배열을 완전 탐색하여 최소 이동 횟수를 구해 문제를 해결했습니다.
3) 코드
* Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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))
|
'Deprecated' 카테고리의 다른 글
[Baekjoon Online Judge] 백준 7576번 토마토(Python) (0) | 2020.03.31 |
---|---|
[Baekjoon Online Judge] 백준 2606번 바이러스(Python) (0) | 2020.03.31 |
[Python] deque 사용법 (0) | 2020.03.30 |
[Baekjoon Online Judge] 백준 1697번 숨바꼭질(Python) (0) | 2020.03.30 |
[Baekjoon Online Judge] 백준 15663번 N과 M (9)(Python) (0) | 2020.03.30 |