백준 / python / 1584. 게임

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

 

문제 요약

501 x 501 지도가 있다. 지도의 일부분을 밟으면 체력이 1 닳고 지도의 일부분은 접근할 수 없다.

(0, 0) 에서 (500, 500) 까지 이동할 때 받는 최소한의 데미지를 구하라.

 

 

풀이 요약

1. bfs 로 푼다. 

2. 큐에는 이동 좌표와 함께 이때까지 받은 데미지를 추가한다.

3. 이미 더 적은 데미지를 가지고 방문한 적이 있다면 큐에 넣지 않는다.

주의사항

1. 그냥 deque 로는 시간초과난다. heap 을 쓰거나 zero-one bfs 를 사용해야한다..

2. 움직일 수 있는 방향이 8방향인지 4방향인지 실수하지 말자.

3. bfs 에서 queue 대신 heap 을 쓰면 dijkstra 다.

4. 올바른 좌표값인지 확인할 때 if x in range(501) 등을 사용하면 x < 0 or x > 500 보다 250배 느려진다.

5. 반복되는 코드를 함수로 만들면 실행속도가 빨라진다.

from sys import stdin
from collections import deque

input = stdin.readline

moves = [
    (0, -1),
    (-1, 0),
    (1, 0),
    (0, 1),
]
graph = [[0] * 501 for _ in range(501)]


def check_rect(num):
    N = int(input())
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        left, right = sorted([x1, x2])
        top, bottom = sorted([y1, y2])

        for x in range(left, right + 1):
            for y in range(top, bottom + 1):
                graph[y][x] = num


def bfs():
    # (damage, x, y)
    q = deque([(0, 0, 0)])

    while q:
        damage, x, y = q.popleft()

        if x == 500 and y == 500:
            return damage

        for dx, dy in moves:
            nx = x + dx
            ny = y + dy

            if 0 <= nx <= 500 and 0 <= ny <= 500:
                if graph[ny][nx] == 2:
                    continue

                ndamage = damage + graph[ny][nx]

                if not graph[ny][nx]:
                    q.appendleft((ndamage, nx, ny))
                else:
                    q.append((ndamage, nx, ny))
                graph[ny][nx] = 2

    return -1


for i in [1, 2]:
    check_rect(i)

print(bfs())