| 시간 제한 | 메모리 제한 |
| 2초 | 1024MB |
문제
통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N * M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j)로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.
등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. i번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 (Ri, Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 (R1, C1), (R2, C2) 사이의 거리는 |R1 - R2| + |C1 - C2|와 같다.
재헌이는 교통 정체가 일어나고 있는 칸을 방문하면 수업에 지각하게 되며, 방문하지 않는다면 지각하지 않고 무사히 수업을 들을 수 있다. K개의 정체 구역에 대한 정보가 주어졌을 때 재헌이가 지각하지 않고 1교시 수업을 들을 수 있을지 알아보자. 또한 재헌이는 최대한 일찍 학교에 도착하려 하기 때문에, 만약 재헌이가 지각하지 않고 수업을 들을 수 있다면 최소 몇 번의 이동으로 수업을 들으러 갈 수 있는지도 구해보자.
입력
첫째 줄에 격자의 크기 N, M이 주어진다. (2 ≤ N, M ≤ 3,000)
다음 줄에 정체 구역의 수 K가 주어진다. (1 ≤ K ≤ 3,000)
다음 K개 줄에 걸쳐 각 정체 구역의 정보 Ri, Ci, Di가 주어진다. (1 ≤ Ri ≤ N, 1 ≤ Ci ≤ M, 0 ≤ Di ≤ 3,000)
(1, 1) 또는 (N, M)에 교통 정체가 일어나고 있는 경우는 주어지지 않는다.
출력
재헌이가 지각하지 않고 수업을 들을 수 있으면 YES를 출력하고, 다음 줄에 최소 이동 횟수를 출력한다.
만약 지각하지 않고 수업을 들을 수 없다면 NO를 출력한다.
풀이
우선 탐색 자체는 너비우선탐색이나 깊이우선탐색을 시도할 수 있다. 탐색하려는 i행 j열의 위치가 정체 구역의 중심지로부터 거리가 R이내인지 확인하는 방법을 생각해보자. 정체 구역 K가 최대 3000개인데 이렇게되면 모든 칸에 대한 탐색에 대해 K번의 탐색을 실시하므로 O(N*M*K)가 된다. 연산횟수가 너무 많아지기 때문에 줄일 수 있는 방법을 생각해보자.
정체 구역의 정보를 받을 때 격자에 탐색할 수 없는 지역을 표시해주면 i행 j열의 칸을 탐색할 때 해당 칸의 정체 구역 포함 여부를 바로 확인할 수 있다. 이 방법으로 O(N * M)으로 탐색 시간을 줄일 수 있다.
하지만 K개의 정체 구역이 모두 최대 크기라면 이 칸들을 확인하는 데에만 O(K * N * M)이 소모된다. 이렇게 되면 거리 직접 계산과 별반 차이가 없기 때문에 또 다른 방법을 찾아야 한다.
정체 구역을 모두 칠하지 않고, 정체 구역의 테두리만 따로 체크해줄 수 있다. 탐색은 상, 하, 좌, 우로 인접한 칸으로만 진행되기 때문에 정체 구역의 내부는 어떻게 되든 상관이 없다. 이렇게 되면 최악의 경우 O(K * N)으로 정체 구역 확인이 가능하고 너비우선탐색까지 O(N * M)으로 실행 가능하다.
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
K = int(input())
D = [(1, 0), (0, 1), (-1, 0), (0, -1)]
board = [[0] * M for _ in range(N)]
for _ in range(K):
r, c, d = map(int, input().split())
r -= 1; c -= 1
board[r][c] = -1
for i in range(d + 1):
j = d - i
dr, dc = r + i, c + j
if dr < N and dc < M:
board[dr][dc] = -1
dr, dc = r - i, c + j
if 0 <= dr < N and dc < M:
board[dr][dc] = -1
dr, dc = r + i, c - j
if dr < N and 0 <= dc < M:
board[dr][dc] = -1
dr, dc = r - i, c - j
if 0 <= dr < N and 0 <= dc < M:
board[dr][dc] = -1
bfs = deque([(0, 0)])
while bfs:
x, y = bfs.popleft()
if x == N - 1 and y == M - 1: break
for dx, dy in D:
dx += x
dy += y
if 0 <= dx < N and 0 <= dy < M and board[dx][dy] == 0:
board[dx][dy] = board[x][y] + 1
bfs.append((dx, dy))
print(f"YES\n{board[-1][-1]}" if board[-1][-1] > 0 else "NO")
solution()
