반응형
최소 거리를 구하는 문제이기 때문에 BFS를 이용한다.
각 방을 노드로, 방과 방 사이를 이동하는데 부숴야하는 벽의 수를 노드 간 이동 비용이라고 했을 때,
벽이 없는 방(0)으로 이동하는데에는 비용이 0, 부숴야 하는 벽(1)으로 이동하는데에는 비용이 1 소모되는
0과 1의 비용을 가진 탐색이 된다.
비용이 0과 1로 나뉘어져있을때에는 deque를 사용해서 매 노드를 탐색할 때마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 1이면 뒤에 추가해주며 탐색을 이어나가면 된다.
그렇게 하면 비용이 적은 경로부터 우선적으로 탐색하고, 가장 적은 비용에 대한 탐색이 끝나고 나서야 비로소 더 큰 비용의 경로를 탐색하기 시작하기 때문에 벽을 최소한으로 부수고 이동하는 경로를 찾을 수 있게 된다.
|
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
|
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
a = []
for i in range(m):
a.append(sys.stdin.readline())
dist = [[-1]*n for _ in range(m)]
dist[0][0] = 0
q = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q.append([0, 0])
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx>=0 and nx<m and ny >=0 and ny<n:
if dist[nx][ny] == -1:
if a[nx][ny] == '0':
q.appendleft([nx, ny])
dist[nx][ny] = dist[x][y]
elif a[nx][ny] == '1':
q.append([nx, ny])
dist[nx][ny] = dist[x][y]+1
print(dist[m-1][n-1])
|
반응형
'Python > 알고리즘' 카테고리의 다른 글
| 트리 순회 (백준 1991, 파이썬) (0) | 2019.09.06 |
|---|---|
| 트리의 높이와 너비 (백준 2250, 파이썬) (0) | 2019.09.06 |
| 이모티콘 (백준 14226, 파이썬) (0) | 2019.08.31 |
| 보석 도둑 (백준 1202, 파이썬) (0) | 2019.08.21 |
| 재귀호출로 최댓값 구하기 (모두의 알고리즘 with 파이썬 4-2) (0) | 2019.07.04 |
