1️⃣ 서론
백준 문제 1261번 알고스팟 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
(1,1) 에서 (N,M) 까지 가면서 벽을 최소한 뚫으며 갈 수 있는 방법을 찾는 문제입니다.
3️⃣ 풀이
일반적인 bfs 방법으로는 벽을 어디서부터 뚫으냐에 따라서 답이 달라질 수 있습니다.
따라서 조금은 다른 방법을 써야합니다.
바로 벽이 없는 곳을 방문했을 때는 큐의 맨앞에 넣는 것입니다.
이 작업을 수행함에 따라 더 비용이 작은 벽을 먼저 항상 방문하고 나서 벽이 있는 곳을 방문하므로
최소의 비용으로 N,M을 방문할 수 있게 됩니다. 그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
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
33
34
import sys
from collections import deque
def bfs():
q.append([0, 0])
while q:
x, y = q.popleft()
for i in range(4):
dx = x + dir[i][0]
dy = y + dir[i][1]
if 0 <= dx < n and 0 <= dy < m and not vis[dx][dy]:
vis[dx][dy] = True
if miro[dx][dy] == 1:
q.append([dx, dy])
count[dx][dy] = count[x][y] + 1
else:
q.appendleft([dx, dy])
count[dx][dy] = count[x][y]
print(count[n - 1][m - 1])
m, n = map(int, input().split())
miro = []
for _ in range(n):
miro.append(list(map(int, sys.stdin.readline().rstrip())))
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
vis = [[False] * m for _ in range(n)]
count = [[0] * m for _ in range(n)]
q = deque()
bfs()
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
