*문제 출처는 백준에 있습니다.
문제 제목: 얼음 미로 / 20926번 (골드 2단계)
문제 사이트: https://www.acmicpc.net/problem/20926
문제 설명

나의 풀이
from heapq import heappush, heappop
# 상 하 좌 우
move = [(0, 1), (0, -1), (-1 ,0), (1, 0)]
def solution(maps):
# 시작/도착 좌표 찾기
tera_y = tera_x = goal_y = goal_x = 0
H, W = len(maps), len(maps[0])
for i in range(H):
for ii in range(W):
if maps[i][ii] == 'E':
goal_y, goal_x = i, ii
if maps[i][ii] == 'T':
tera_y, tera_x = i, ii
# 다익스트라: 좌표별 최소 비용
INF = 10**18
dist = [[INF] * W for _ in range(H)]
dist[tera_y][tera_x] = 0
# 우선순위 큐(비용, y, x)
pq = []
heappush(pq, (0, tera_y, tera_x))
while pq:
cur_cost, ry, rx = heappop(pq)
if cur_cost != dist[ry][rx]:
continue
if (ry, rx) == (goal_y, goal_x):
return cur_cost # 최단 비용 확정
for iy, ix in move:
res = r_move(maps, ry, rx, iy, ix) # 원래 r_move 유지
if res is None:
continue
y, x, c_dis = res
nd = cur_cost + c_dis
if nd < dist[y][x]:
dist[y][x] = nd
heappush(pq, (nd, y, x))
return -1 # 도달 불가
def r_move(maps, ry, rx, my, mx):
"""
(ry,rx)에서 (my,mx)로 미끄러졌을 때의 도착 좌표와 누적 시간 반환.
- 시작 타일 비용 제외
- 출구(E) 타일 비용 제외
- 구멍(H)·절벽은 None (이동 불가)
- 바위(R)는 직전 칸에서 멈춤
"""
H, W = len(maps), len(maps[0])
y, x, dis = ry, rx, 0
while True:
# 이동 전 위치
py, px = y, x
# 한 칸 이동
y += my
x += mx
# 절벽
if y < 0 or y >= H or x < 0 or x >= W:
return None
cell = maps[y][x]
# 구멍
if cell == 'H':
return None
# 바위 → 직전 칸에서 멈춤
if cell == 'R':
return (py, px, dis)
# 출구 → 출구 비용 제외
if cell == 'E':
return (y, x, dis)
# 숫자면 비용 누적 (시작 타일은 이미 제외됨)
if '0' <= cell <= '9':
dis += ord(cell) - ord('0')
# 'T'는 시작 지점(비용 0), 그냥 통과
if __name__=="__main__":
w, h = map(int, input().split())
maps = [list(input().strip()) for _ in range(h)]
print(solution(maps))

※ 알아야 할 것
from collections import deque
def solution(maps):
answer = 999999999999
# 상 하 좌 우
move = [(0, 1), (0, -1), (-1 ,0), (1, 0)]
# 초기 위치 변수
tera_y, tera_x, goal_y, goal_x = 0, 0, 0, 0
# 테라 위치, 목적지 저장
for i in range(len(maps)):
for ii in range(len(maps[0])):
if maps[i][ii] == 'E':
goal_y, goal_x = i, ii
if maps[i][ii] == 'T':
tera_y, tera_x = i, ii
# 현재 위치(y, x), 이동거리
dq = deque([(tera_y, tera_x, 0)])
# 중복 방지
visited = set()
visited.add((tera_y, tera_x))
while dq:
ry, rx, dis = dq.popleft()
# 도착점에 도착했을 때
if (ry, rx) == (goal_y, goal_x):
answer = min(dis, answer)
continue
for iy, ix in move:
y, x, c_dis = r_move(maps, ry, rx, iy, ix)
# 빠지는 경우는 제외
if y == -1 and x == -1:
continue
if (y, x) == (ry, rx):
continue
if (y, x) not in visited:
visited.add((y, x))
dq.append((y, x, c_dis + dis))
if answer == 999999999999:
return -1
else:
return answer
def r_move(maps, ry, rx, my, mx):
y, x, dis = ry, rx, 0
while True:
# 이동하기 전 위치
ry = y
rx = x
# 이동하기 후 위치
y += my
x += mx
# 밖으로 나가는 경우
if 0 > y or y >= len(maps) or 0 > x or x >= len(maps[0]):
return -1, -1, 0
# 구멍인 경우
elif maps[y][x] == 'H':
return -1, -1, 0
# 돌인경우
elif maps[y][x] == 'R':
return ry, rx, dis
# 출구인 경우
elif maps[y][x] == 'E':
return y, x, dis
# 이외 숫자인 경우
elif '0' <= maps[y][x] <= '9':
# 시간을 더한다
dis += int(maps[y][x])
if __name__=="__main__":
w, h = map(int, input().split())
# 지도
maps = [list(input()) for _ in range(h)]
print(solution(maps))
BFS로 풀게되면 가중치 값을 통한 최적의 경로를 찾지 못한다 그리고 visited를 통해 중복 경로를 제거하게되면 다른 경우의 수를 제거하게 된다 그러므로 다익스트라로 푸는게 정석입니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 욕심쟁이 판다 / 1937번 / Python (0) | 2025.09.12 |
|---|---|
| 백준 / 텔레포트 / 16958번 / Python (1) | 2025.09.10 |
| 백준 / 회전 초밥 / 15961번 / Python (2) | 2025.07.28 |
| 백준 / 두 배열의 합 / 2143번 / Python (3) | 2025.07.25 |
| 백준 / 분수 합 / 1735번 / Python (2) | 2025.07.09 |