[Python] 1584번 게임

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

1584번: 게임

---

 

22/11/20

 

 

전형적인 그래프 탐색 문제로, 간선의 가중치 정보가 0과 1밖에 없기 때문에 다익스트라 대신 0-1 BFS로 풀어도 무방한 문제이다.

 

2022.09.02 - [백준 문제 풀이] - [Python] 13549번 숨바꼭질 3 (추후 보강 예정)

[Python] 13549번 숨바꼭질 3 (추후 보강 예정)

0-1 BFS는 이 문제와 같이, 최단 거리혹은 최단 시간을 구할 때 항상 간선의 가중치가 0인 부분 먼저 탐색을 진행하는 BFS라고 생각하면 된다.

---

 

문제 접근 방식:

 

 

먼저 $(0, 0)$에서 시작해서 $(500, 500)$으로 간다고 했으므로, $501*501$크기의 이차원 배열 $graph$를 선언해 주었다.

 

이후 위험한 구역은 $1$로, 죽음의 구역은 $2$로 표시한다.

 

이후 BFS를 진행하는데, 현재 위치와 깎인 생명력을 큐에다 넣어주었다.

 

방문 처리는 내가 방문한 곳을 죽음의 구역으로 변형시킴으로써 다시는 못 오게 해 주었다.

 

여기서 중요한 점은 append를 할 때, 생명력이 깎이지 않는 상황이면 appendleft를 해주고 그렇지 않다면 그냥 append를 해줬다는 점이다.

 

생명력이 깎이지 않는 상황을 우선시함으로써, 최대한 생명력이 적게 깎이도록 탐색할 수 있다.(0-1 BFS)

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1584번 게임
# 그래프 이론, 그래프 탐색, 0-1 BFS, 다익스트라
'''
접근 방법:
생명 감소가 0인 안전한 구역을 중심으로 탐색한다.
'''
import sys
from collections import deque
input = sys.stdin.readline

graph = [[0 for _ in range(501)] for _ in range(501)]
N = int(input())  # 위험한 구역의 수
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    for row in range(min(x1, x2), max(x1, x2)+1):
        for col in range(min(y1, y2), max(y1, y2)+1):
            graph[row][col] = 1  # 위험한 구역은 1로, 죽음의 구역은 2로 표현하자.
M = int(input())
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    for row in range(min(x1, x2), max(x1, x2)+1):
        for col in range(min(y1, y2), max(y1, y2)+1):
            graph[row][col] = 2  # 위험한 구역은 1로, 죽음의 구역은 2로 표현하자.

# 생명의 감소는 구역에 들어갈 때만, 영향을 미친다. 따라서 시작을 0으로 잡아도 상관 없음.
queue = deque()
queue.append((0, 0, 0))  # row, col, time
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
while queue:
    row, col, time = queue.popleft()
    if (row, col) == (500, 500):
        print(time)
        break
    else:
        for i in range(4):
            now_row, now_col = row+dr[i], col+dc[i]
            if now_row > 500 or now_row < 0 or now_col > 500 or now_col < 0:
                continue
            if graph[now_row][now_col] == 0:
                graph[now_row][now_col] = 2
                queue.appendleft((now_row, now_col, time))
            elif graph[now_row][now_col] == 1:
                graph[now_row][now_col] = 2
                queue.append((now_row, now_col, time+1))
else:
    print(-1)