[알고리즘/백준] 1584번 게임 Python 파이썬

 

이번 문제는 이해하는데 어려웠던 문제였습니다.

 

 

세준이가 0,0 에서 500, 500 으로 이동할 때 잃는 생명의 최솟 값을 구하는 문제로 BFS를 적용해서 풀었습니다. 풀면서 고려해야하는 점은 사방면 이동, 위험과 죽음 영역이 겹쳤을 때 처리 방법, 최솟값을 구해야한다는 점입니다.

 

BFS로 풀다가 계속 오류나서 풀이를 보고 깨달음을 얻었습니다. 

 

먼저, 다음과 같은 코드로 통과하였습니다.

 

import sys
from collections import deque
input = sys.stdin.readline

map_list = [[0]*501 for _ in range(501)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

danger = []
death = []

def update_map(x1, y1, x2, y2, n):
    for i in range(min(x1, x2), max(x1,x2)+1):
        for j in range(min(y1,y2), max(y1,y2)+1):
            map_list[i][j] = n

N = int(input())
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    update_map(x1,y1,x2,y2,1)

M = int(input())
for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    update_map(x1,y1,x2,y2,2)

answer = 0
visited = [[False]*501 for _ in range(501)]
q = deque()
q.append((0,0,0))
visited[0][0] = True
check = False

while q:
    x, y, life = q.popleft()
    if x == 500 and y == 500:
        check = True
        answer = life
        break

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx <= 500 and 0 <= ny <= 500 and visited[nx][ny] == False:
            if map_list[nx][ny] == 0:
                q.appendleft((nx, ny, life))
                visited[nx][ny] = True
            elif map_list[nx][ny] == 1:
                q.append((nx, ny, life+1))
                visited[nx][ny] = True

if check == True:
    print(answer)
else:
    print(-1)

 

어떤 부분에서 오류 났는지와 어떻게 하면 효율적으로 풀 수 있는지 찾아보았고 이를 이해하기 위해 아래와 같이 직접 시물레이션을 돌려보았습니다. 각 칸의 앞 숫자가 잃은 생명의 수치 () 안에 숫자가 검사하는 순서입니다.

 

(왼) 0 구역을 미리 탐색하지 않았을 때 결과 / (오) 0 구역 먼저 탐색했을 때 결과

 

위의 코드에서 appendleft 를 사용해서 0 즉 생명이 소모되지 않는 지역에 들어오면 생명이 소모되는 지역보다 먼저 검사해주는 것이 중요한 포인트입니다. 만약에 그렇지 않을 경우 위의 사진 왼쪽과 같이 최솟값을 구할 수 없게 됩니다. 

 

갈수록 점점 어려워지고 생각할 부분이 많아지는 것 같습니다.