[BOJ 2424, Python 3] 부산의 해적

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

2424번: 부산의 해적

해적이 언제 해당 지역을 볼 수 있는지 빠르게 확인하는 아이디어 때문에 난이도가 높은 것 같은데 코드양만 많지 의외로 쉽습니다.

 

 

 

풀이

수아가 움직일 때, 해적은 가만히 있거나, 움직이는 것을 선택할 수 있는 상태에서 해적의 움직임과 상관없이 수아가 보물을 얻을 수 있을지 구하라는 문제입니다.

해적의 움직임과 상관이 없으려면 해적은 최단시간안에 모든 지역을 볼 수 있어도 수아가 보물을 찾는데 지장이 없어야 한다는 것이니까 수아뿐만 아니라 해적도 그래프 탐색이 필요합니다.

 

여기서 해적을 BFS로 돌리면서 동시에 while문으로 상하좌우 끝까지 값을 갱신하는 방법도 있지만, 좀 더 좋은 방법이 존재합니다.

일단 BFS를 돌리고, 한 줄에서 가로방향으로 볼 수 있는 곳의 구간을 구한 후 최솟값을 찾아서 그 구간을 전부 최솟값으로 설정해주는 것입니다. 세로 방향도 마찬가지구요.

 

예제 1번을 가지고 예를 들자면 아래 그림처럼 가로 방향으로 구간별 최솟값을 구해서 구간에 있는 값을 모두 최솟값으로 바꿔주는 것입니다.

 

세로 방향도 마찬가지로 아래 그림처럼 해주면 됩니다.

 

 

이 방식으로 코드를 짜면 빠르게 답을 구할 수 있게 됩니다.

다른 분 코드는 보지 않아서 모르겠지만, 아마 이 탐색 방법 때문에 난이도가 높은 것 같습니다.

 

수아를 BFS 돌릴 때, 해적이 해당 칸을 관측 할 수 있는 시간보다 빠르게 도착할 수 있으면 해당 칸으로 이동할 수 있다고 생각하여 BFS를 돌리면 됩니다.

 

코드

from collections import deque
input = __import__('sys').stdin.readline
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
 
n, m = map(int, input().split())
arr = [[*input().strip()] for _ in range(n)]
p_see = [[float('inf')] * m for _ in range(n)] # 해적이 언제 볼 수 있는지 확인하는 배열
visit = [[-1] * m for _ in range(n)] # 수아가 이동할 때 사용할 방문 배열
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'T': tx, ty = i, j
 
# 해적부터 이동
q = deque()
p_visit = [[-1] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'V':
            p_visit[i][j] = 0
            q.append([i, j])
while q:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] != 'I' and p_visit[nx][ny] == -1:
            q.append([nx, ny])
            p_visit[nx][ny] = p_visit[x][y] + 1
 
for i in range(n):
    stack = []
    val = [0, 0, float('inf')] # 좌표 idx_0 ~ idx_1 까지 idx_2값으로 채움
    for j in range(m):
        if arr[i][j] != 'I': val[2] = min(val[2], p_visit[i][j]); val[1] = j
        elif arr[i][j] == 'I' and val[2] != float('inf'):
            stack.append(val)
            val = [j+1, j+1, float('inf')]
        else: val = [j+1, j+1, float('inf')]
    if val[2] != float('inf'): stack.append(val)
    for s, e, val in stack:
        for j in range(s, e+1):
            p_see[i][j] = val
 
for j in range(m):
    stack = []
    val = [0, 0, float('inf')] # 좌표 idx_0 ~ idx_1 까지 idx_2값으로 채움
    for i in range(n):
        if arr[i][j] != 'I': val[2] = min(val[2], p_visit[i][j]); val[1] = i
        elif arr[i][j] == 'I' and val[2] != float('inf'):
            stack.append(val)
            val = [i+1, i+1, float('inf')]
        else: val = [i+1, i+1, float('inf')]
    if val[2] != float('inf'): stack.append(val)
    for s, e, val in stack:
        for i in range(s, e+1):
            p_see[i][j] = min(p_see[i][j], val)
 
q = deque()
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'Y': visit[i][j] = 0; q.append([i, j])
 
while q:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] != 'I' and visit[nx][ny] == -1 and visit[x][y] + 1 < p_see[nx][ny]:
            q.append([nx, ny])
            visit[nx][ny] = visit[x][y] + 1
 
if visit[tx][ty] != -1 and visit[tx][ty] < p_see[tx][ty]: print('YES')
else: print('NO')