백준 / 얼음 미로 / 20926번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 얼음 미로 / 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를 통해 중복 경로를 제거하게되면 다른 경우의 수를 제거하게 된다 그러므로 다익스트라로 푸는게 정석입니다!