[백준/27453] 귀엽기만 한 게 아닌 한별 양 (Python)

Problem : https://www.acmicpc.net/problem/27453

27453번: 귀엽기만 한 게 아닌 한별 양

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:42:55

 

---

 

문제 설명

 

 

당신은 엄청난 불행 체질을 갖고 태어났다. 다행히 당신에게는 불행 체질을 받아내 주는 여자친구 한별이가 있다. 한별이는 운동신경이 매우 뛰어나 당신에게 닥치는 불상사들을 막아내주곤 한다. 하지만 그런 한별이에게도 한계가 있기에, 연속해서 너무 많은 불상사들이 생기는 경우에는 당신을 온전하게 지켜주지 못하게 된다.

현재 당신과 한별이는 학교에서 집으로 귀가하고 있다. 마을은 N x M 형태의 격자 모양이며, 당신과 한별이는 격자에서 상하좌우로 인접한 칸으로만 이동할 수 있다. 단, 일부 칸에는 벽이 있어 이동할 수 없다. 또, 당신은 한별이에게 길치처럼 보이고 싶지 않기 때문에, 바로 직전에 방문한 칸으로 돌아가는 행동은 하지 않는다.

오늘은 한별이가 당신의 집으로 놀러 가기로 한 날이기 때문에, 집으로 최대한 빨리 가려고 한다. 당신은 십수 년간의 경험을 바탕으로 마을의 각 좌표마다 일어나는 불상사의 개수를 미리 알아차릴 수 있다. 만약 가장 최근 지나온 
3개 이하 칸에 있는 불상사의 개수 합이 K 개를 넘으면, 한별이도 당신을 지켜주지 못해 부상을 입게 된다. 또, 당신의 불행 체질은 정말 엄청나기 때문에, 방문한 칸에 다시 방문하더라도 매번 같은 개수의 불상사가 다시 일어나게 된다. 과연 당신은 부상을 입지 않고 안전하게 귀가할 수 있을까?

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 마을의 세로 크기 N, 가로 크기 M, 한별이가 연속해서 막을 수 있는 불상사의 개수 K가 주어진다. ( 2 <= N, M <= 1000, 0 <= K <= 27 )

다음 N개의 줄에 걸쳐 마을의 상태가 주어진다. 각 줄은 길이 M의 문자열로 주어진다. S는 학교, H는 집을 의미하고, X는 이동할 수 없는 벽을 의미한다. 이외의 칸에는 각 좌표에서 일어나는 불상사의 개수가 0부터 9까지의 숫자로 주어진다. 학교와 집은 각각 한 개씩만 존재하며, 학교와 집에서는 불상사가 일어나지 않는다.

 

출력

 

학교에서 집으로 안전하게 이동할 수 있을 때, 가능한 경로 중 최단 거리를 출력하시오. 만약 안전하게 귀가하지 못한다면 -1을 출력한다.

 

입력 예시

 

6 6 4
S1113X
33323X
11211X
13311X
1XXXXX
11111H

 

출력 예시

 

20

 

 

---

 

풀이

 

한 칸에서 다음 칸으로 이동할 때, 중요한 영향을 미치는 요소는 진입 방향이 될 것이다. 다음 칸으로 이동할 때의 합은 현재 칸과 현재 바로 이전의 칸이고, 바로 이전의 칸은 현재 칸의 진행 방향을 통해 알 수 있다. 즉 우리는 좌표값 및 그 좌표에 진입한 방향을 기록해야 한다. 또한 다음 칸 + 현재 칸 + 이전 칸의 합이 K 이하여야 함에 주의하자.

 

이후에는 일반 상황처럼 BFS를 수행하면 된다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
MAX = 10
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

N, M, K = map(int, input().split())
maps = []
for i in range(N) :
  _maps = input().strip()
  for j in range(M) :
    if _maps[j] == 'S' :
      sx, sy = j, i
    if _maps[j] == 'H' :
      ex, ey = j, i
  maps.append(_maps)

visited = [[[False]*4 for _ in range(M)] for _ in range(N)]
q = deque([(sx, sy, -1, -1, 0, 0, 0)])
flg = False

while q :
  x, y, px, py, k0, k1, t = q.popleft()
  if x == ex and y == ey :
    flg = True
    break
  for i in range(4) :
    ax, ay = x + dx[i], y + dy[i]
    if -1 < ax < M and -1 < ay < N :
      if maps[ay][ax] == 'X' or (px, py) == (ax, ay) :
        continue
      new_k = 0 if maps[ay][ax] in 'SH' else int(maps[ay][ax])
      if k0 + k1 + new_k > K :
        continue
      if not visited[ay][ax][i] :
        visited[ay][ax][i] = True
        q.append((ax, ay, x, y, k1, new_k, t+1))
print(t if flg else -1)

풀이 완료!