[파이썬/python] 백준 - 1584 게임

문제

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

---

문제 설명

1.   위험한 지역에서 탈출하는 게임을 해야한다. 이 게임에는 세 가지 구역이 존재한다.
   1. 들어갈 수 없는 죽음의 구역
   2. 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역
   3. 자유롭게 움직일 수 있는 안전한 구역
2. 이 때 시작점은 (0,0)이고 도착점은 (500,500)이다. 이동 방향은 상, 하, 좌, 우로 이동할 수 있다. (게임판은 벗어날 수 없다.)
3. (0,0)에서 (500,500)으로 갈 때 잃는 생명의 최솟값을 구해라.
4. 주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다.

 

---

풀이

보통 그래프로 문제가 주어지는 데 위치가 2차원 배열로 주어져서 처음에 어떻게 접근해야 할지 고민했다.

 

문제의 핵심은 문제 설명의 4번이다.

 

주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는 더 심한 구역이 해당된다.

이 말을 아래와 같이 해석할 수 있다.

 

안전한 구역은 cost = 0

위험한 구역은 cost = 1

죽음의 구역은 가로막힌 벽

 

이렇게 보면 좀 더 확신이 생긴다. 죽음의 구역은 지나갈 수 없는 벽이고, 안전한 구역으로 갈 때는 0의 코스트가 들고, 위험한 구역으로 갈 때는 1의 코스트가 드는 것이다.

 

그럼 이제 문제 이해를 끝냈으니 이를 2차원 배열에 표현하기만 하면 된다.

 

나는 게임판의 크기와 동일한 cost 배열을 만든 후 조건에 맞게 해당 배열을 값을 삽입했다.

 

예를 들면 이런 식이다.

게임판의 크기가 4*4라고 가정하고 아래와 같은 입력이 들어오면

1
2 0 0 2
1
0 0 0 0

[1,1,1,0,0]

[1,1,1,0,0]

[1,1,1,0,0]

[0,0,0,0,0]

[0,0,0,0,0]

이런 식으로 배열을 모두 갱신한다.

 

배열 갱신이 모두 끝나면 기존 다익스트라 로직과 동일하게 진행하면 된다.

 

사실 전형적인 다익스트라 기본 문제이다. 하지만 보통은 문제에서 주어지는 cost를 직접 배열로 만들어서 사용해야 한다는 점이 약간의 차별점이라고 생각한다.

 

생각보다 이런 식으로 약간 꼬아서 나오는 경우가 많이 있기 때문에 항상 문제를 풀 때 이런 방식으로도 접근할 수 있구나를 생각하면서 문제를 풀어야 할 것 같다.

 

 

---

코드

import sys
import heapq
input = sys.stdin.readline

R,C = 501,501
INF = sys.maxsize
dy = [0,1,0,-1]
dx = [1,0,-1,0]

cost = [[0 for _ in range(R)] for _ in range(C)]

def init_board(r1,c1,r2,c2, value):
    for r in range(min(r1,r2), max(r1,r2)+1):
        for c in range(min(c1,c2), max(c1,c2)+1):
            cost[r][c] = value

for i in range(int(input())):
    r1,c1,r2,c2 = map(int,input().split())
    init_board(r1,c1,r2,c2, 1)

for i in range(int(input())):
    r1,c1,r2,c2 = map(int,input().split())
    init_board(r1,c1,r2,c2, 2)

dist = [[INF for _ in range(R)] for _ in range(C)]
dist[0][0] = 0

hq = []
heapq.heappush(hq, (0,0,0))

while hq:
    cur_dist,y,x = heapq.heappop(hq)

    if dist[y][x] < cur_dist:
        continue
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        
        if ny < 0 or ny > R-1 or nx < 0 or nx > C-1 or cost[ny][nx] == 2:
            continue
        
        if cur_dist + cost[ny][nx] < dist[ny][nx]:
            dist[ny][nx] = cur_dist + cost[ny][nx]
            heapq.heappush(hq,(dist[ny][nx], ny, nx))

print(dist[R-1][C-1] if dist[R-1][C-1] != INF else -1)

---

시간복잡도

• 다익스트라의 시간 복잡도 $O(ElogV)$
  • $V = R*C$, $E = 4*V$이다.
  • $V$는 배열의 크기인 $R*C$ $C$는 간선의 총개수인 $4*V$
  • 즉 시간복잡도는 약 $O(250000*18)$ = 약 $O(10^6)$정도로 예상된다.