코딩테스트/백준
[백준] 2178번 미로 탐색 / 파이썬(python)
Jiwon_C
2021. 5. 19. 23:57
# 문제 링크
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
# Soultion
BFS를 이용하여 최단거리를 푸는 문제이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from collections import deque
n,m = map(int,input().split())
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs(a,b):
queue = deque([[a,b]])
while(queue):
x,y = queue.popleft()
for i in range(4):
xx = x+dx[i]
yy = y+dy[i]
if 0<=xx<n and 0<=yy<m and graph[xx][yy]==1:
queue.append([xx,yy])
graph[xx][yy] = graph[x][y]+1
bfs(0,0)
print(graph[n-1][m-1])
|
cs |
11. 큐를 생성하여 처음 시작좌표를 넣어준다.
12. 큐가 채워진 동안 계속 반복
13. 큐에서 제일 첫번째 원소를 뽑아온 뒤, 그 좌표를 기준으로 이동을 한다.
18. x,y 좌표가 올바른 값이고, 새로운 길(1)이면 큐의 마지막에 넣어준다.
20. 새로운 길의 최단거리를 1더해준다.