[백준] 게임 (1584번)

문제 링크:

https://www.acmicpc.net/problem/1584

회고:

다익스트라로 해결

• 안전지역, 위험지역, 죽음지역에 대한 정보를 나타내는 graph 생성:
  • (0, 0) ~ (500, 500) 까지 행/렬 각각 501칸으로 이뤄진 2차원 리스트
  • 안전지역의 값: 0 / 위험지역의 값: 1 / 죽음지역의 값: 2
  • 죽음지역의 값은 지나다니지 못하도록 해야 함
    안전지역, 위험지역은 지나가게 될 경우 해당 value 만큼 최소거리가 추가됨
• 최소 거리를 나타내는 distance 생성:
  • graph 변수와 동일한 크기
  • 시작 위치는 (0, 0)이고, 시작 위치까지의 최단거리는 항상 0이다.
  • ex) distance[x][y]: 시작 위치 (0, 0)으로부터 (x, y)까지의 최단 거리
• graph 밖으로 벗어나지 않고 죽음 지역이 아닌 경우에 한하여, 동서남북으로 그 다음 최단 거리를 찾아서 heap에 추가. 추가할 때는 (최단 거리 정보, x좌표, y좌표) 정보를 넣어준다. 힙큐를 사용하기 때문에 최단 거리가 짧을 수록 heap의 앞부분으로 정렬되는 점 참고
• heap에서 최단 거리가 가장 짧은 것을 꺼내어, 최단 거리 정보를 업데이트 해준다.

python

import sys
from heapq import heappush, heappop

INF = 1e9


def update_graph(danger_value, *args):
    global graph

    x1, y1, x2, y2 = args

    for i in range(min(x1, x2), max(x1, x2) + 1):
        for j in range(min(y1, y2), max(y1, y2) + 1):
            graph[i][j] = danger_value


def solution():
    # 최단 거리 정보
    distance = [[INF] * 501 for _ in range(501)]

    # 시작 위치 거리 설정
    distance[0][0] = 0

    # 방향: 왼쪽, 오른쪽, 아래, 위
    dxs = (0, 0, 1, -1)
    dys = (-1, 1, 0, 0)

    # 시작 위치에 대한 다음 최단 거리 구하기 / heap: (거리, x좌표, y좌표) 들의 리스트
    heap = []
    for x, y in [(0, 1), (1, 0)]:
        if graph[x][y] != 2:
            heappush(heap, (graph[x][y], x, y))

    while heap:
        value, x, y = heappop(heap)

        # 최단 거리 구하기
        if value < distance[x][y]:
            distance[x][y] = value

            if x == 500 and y == 500:
                break

            for dx, dy in zip(dxs, dys):
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx > 500 or ny < 0 or ny > 500:
                    continue

                if graph[nx][ny] != 2 and value + graph[nx][ny] < distance[nx][ny]:
                    heappush(heap, (value + graph[nx][ny], nx, ny))

    return -1 if distance[500][500] == INF else distance[500][500]


if __name__ == "__main__":
    # 0: 자유 롭게 다닐수 있는 곳, 1: 위험 지역, 2: 죽음 지역
    graph = [[0] * 501 for _ in range(501)]

    # 위험 구역 정보
    for _ in range(int(input())):
        update_graph(1, *map(int, sys.stdin.readline().split()))

    # 죽음 구역 정보
    for _ in range(int(input())):
        update_graph(2, *map(int, sys.stdin.readline().split()))

    print(solution())

# 입력값 

1
0 0 499 500
0

# 출력값

499