[백준/2424] 부산의 해적 (Python)

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

2424번: 부산의 해적

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:29:29

 

---

 

문제 설명

 

 

수아는 보물 지도를 얻었다. 보물 지도는 N × M 크기이고 1 × 1크기의 정사각형으로 나누어져 있다. 보물 지도의 각 칸은 바다이거나 섬의 일부이다. 그리고, 지도에는 보물과 부산의 해적선의 위치도 있다. 마지막으로 수아는 자신의 위치를 지도에 표시했다.

자 이제, 수아는 보물을 가지기 위한 경로를 정해야 한다. 경로는 현재 수아의 위치에서 시작해야 하고, 보물의 위치에서 끝나야 한다. 매번 수아가 이동할 때, 수아는 위, 아래, 오른쪽, 왼쪽 중의 한 방향으로 이동해야 하고, 섬으로 들어가면 안 된다. 하지만, 부산의 해적도 수아와 같은 방식으로 이동할 것이므로, 부산의 해적을 조심해야 한다. 매번 수아가 이동한 후에, 해적은 수아의 이동에 대해서 이동할지 멈춰있을지 결정할 수 있다. 수아의 움직임과 해적의 반응을 턴이라고 부르면, 매 턴이 지난 후에 다음과 같이 2가지 방법으로확인할 수 있다.

만약 수아가 해적과 바라보고 있다면 (해적과 수직선, 수평선상에 수아가 있고, 오직 그 사이에 바다만 있을 때) 수아는 죽는다.
만약, 수아가 아직 죽지 않았고, 보물 위치에 있다면, 수아는 보물은 얻은 것이다.
부산의 해적이 어떻게 움직이건 관계없이 수아가 죽지않고 보물을 얻을 수 있는 경로를 구하는 프로그램을 작성하시오. 

 

 

입력 및 출력

 

입력

 

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 구성되어 있는데, .은 바다이고, I는 섬이고, V는 해적의 위치이고, Y는 현재 수아의 위치이고, T는 보물의 위치이다. V, Y, T는 모두 한 번씩 등장한다. (1 ≤ N, M ≤ 700)

 

출력

 

첫째 줄에 수아가 보물을 얻을 수 있으면 YES를 출력하고, 그렇지 않으면 NO를 출력한다.

 

입력 예시

 

5 7
Y.....V
..I....
..IIIII
.......
...T...

 

출력 예시

 

YES

 

 

---

 

풀이

 

해적이 먼저 BFS로 탐색을 진행하며 최소 도달 시간을 기록하고, 그 다음 수아가 해적의 최소 도달 시간 내에 BFS로 보물까지 도달할 수 있는지 여부를 탐색하면 된다. 이 BFS에는 O(NM)의 시간복잡도가 소요된다.

 

문제는 해적이 도달한 위치에서 수직, 수평선상에 수아가 존재할 수 없다는 점이다. 즉 수직, 수평선상 역시 최소 도달 거리를 업데이트해야 한다. 하지만 BFS 진행 도중 일일히 이들을 검사하게 되면 시간적으로 비효율적이다.

 

발상을 전환하여, (x, y)좌표 내에 영향을 미칠 수 있는 해적의 최소 도달시간을 생각해 보자.

 

어떤 위치 (x, y)에서 영향을 받는 구간은 

• x축상의 도달 가능한 위치들의 최솟값과
• y축상의 도달 가능한 위치들의 최솟값

이 된다. 여기서, 이 x축상의 구간과 y축상의 구간은 동일한 값(구간 최솟값)을 가짐을 알 수 있다. 즉 다음과 같이 시각적으로 나타낼 수 있다.

 

즉 먼저 BFS로 해적의 최소 도달 시간만을 업데이트하고,

• x축을 기준으로 나뉘는 각 구간과 그 구간의 최솟값을 업데이트,
• 그리고 y축도 동일하게 각 구간에 그 구간의 최솟값을 업데이트하면
• O(NM(N+M))의 시간복잡도로 최소 구간을 업데이트할 수 있다.

 

풀이 코드

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

N, M = map(int, input().split())
MAX = N*M+1
maps = [input().strip() for _ in range(N)]
pq, sq = deque(), deque()

p_visited = [[MAX]*M for _ in range(N)]
isdead = [[MAX]*M for _ in range(N)]

def init() :
  global treasure
  for i in range(N) :
    for j in range(M) :
      if maps[i][j] == 'T' :
        treasure = (j, i)
      if maps[i][j] == 'Y' :
        sq.append((j, i, 0))
      if maps[i][j] == 'V' :
        pq.append((j, i, 1))
        p_visited[i][j] = 1

def shoot() :
  for i in range(N) :
    prev, minval = 0, p_visited[i][0]
    for j in range(1, M) :
      if maps[i][j] == 'I' :
        for k in range(prev, j) :
          isdead[i][k] = min(isdead[i][k], minval)
        prev, minval = j, p_visited[i][j]
      else :
        minval = min(minval, p_visited[i][j])
    for k in range(prev, M) :
      isdead[i][k] = min(isdead[i][k], minval)
    
  for i in range(M) :
    prev, minval = 0, p_visited[0][i]
    for j in range(1, N) :
      if maps[j][i] == 'I' :
        for k in range(prev, j) :
          isdead[k][i] = min(isdead[k][i], minval)
        prev, minval = j, p_visited[j][i]
      else :
        minval = min(minval, p_visited[j][i])
    for k in range(prev, N) :
      isdead[k][i] = min(isdead[k][i], minval)
      
def p_bfs() :
  while pq :
    x, y, cnt = pq.popleft()
    for i in range(4) :
      ax, ay = x + dx[i], y + dy[i]
      if -1 < ax < M and -1 < ay < N and maps[ay][ax] != 'I' and p_visited[ay][ax] > cnt :
        p_visited[ay][ax] = cnt
        pq.append((ax, ay, cnt+1))
  shoot()

def s_bfs() :
  while sq :
    x, y, cnt = sq.popleft()
    if (x, y) == treasure :
      return True
    for i in range(4) :
      ax, ay = x + dx[i], y + dy[i]
      if -1 < ax < M and -1 < ay < N and maps[ay][ax] != 'I' and isdead[ay][ax] > cnt+1 :
        isdead[ay][ax] = cnt+1
        sq.append((ax, ay, cnt+1))
  return False

init()
p_bfs()
print("YES" if s_bfs() else "NO")

풀이 완료!