[BOJ][🟡3][백준#26009] 험난한 등굣길

문제 출처

BAEKJOON Online Judge #26009

문제

통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 $N \times M$ 인 격자로 나타낼 수 있는데, $i$행 $j$열에 해당하는 칸을 $(i, j)$로 나타낼 때 재헌이는 현재 $(1, 1)$에, 학교는 $(N, M)$에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다. 등굣길은 순탄치만은 않은데, 이 지역에는 $K$개의 정체 구역이 있다. $i$번째 정체 구역은 세 정수 $R_i, C_i, D_i$로 표현되며, 이는 $(R_i, C_i)$로부터 거리가 $D_i$ 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 $(R_1, C_1), (R_2, C_2)$ 사이의 거리는 $|R_1 - R_2| + |C_1 - C_2|$와 같다. 재헌이는 교통 정체가 일어나고 있는 칸을 방문하면 수업에 지각하게 되며, 방문하지 않는다면 지각하지 않고 무사히 수업을 들을 수 있다. $K$개의 정체 구역에 대한 정보가 주어졌을 때 재헌이가 지각하지 않고 1교시 수업을 들을 수 있을지 알아보자. 또한 재헌이는 최대한 일찍 학교에 도착하려 하기 때문에, 만약 재헌이가 지각하지 않고 수업을 들을 수 있다면 최소 몇 번의 이동으로 수업을 들으러 갈 수 있는지도 구해보자.

입력

첫째 줄에 격자의 크기 $N, M$이 주어진다. $(2 \le N, M \le 3\ 000)$ 다음 줄에 정체 구역의 수 $K$가 주어진다. $(1 \le K \le 3\ 000)$ 다음 $K$개 줄에 걸쳐 각 정체 구역의 정보 $R_i, C_i, D_i$가 주어진다. $(1 \le R_i \le N, 1 \le C_i \le M, 0 \le D_i \le 3\ 000)$ $(1, 1)$ 또는 $(N, M)$에 교통 정체가 일어나고 있는 경우는 주어지지 않는다.

출력

재헌이가 지각하지 않고 수업을 들을 수 있으면 YES를 출력하고, 다음 줄에 최소 이동 횟수를 출력한다. 만약 지각하지 않고 수업을 들을 수 없다면 NO를 출력한다.

예제

예제 1

입력

5 5
2
4 2 1
2 4 0

출력

YES
8

예제 2

입력

5 5
2
4 2 1
2 4 1

출력

NO

예제 3

입력

4 7
3
1 3 0
1 3 1
4 5 1

출력

YES
11

My Sol

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

def main():
    global mat, I, J

    # N번동안 차 확인
    for _ in range(N):
        if not check_main(): return False

    # BFS
    Q = deque([(0,0)])
    mat[0][0] = 1
    while Q:
        ni, nj = Q.popleft()
        for di, dj in ((1,0),(0,1),(-1,0),(0,-1)):
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): continue
            if mat[si][sj]: continue

            mat[si][sj] = mat[ni][nj]+1
            if si==I-1 and sj==J-1: return True
            Q.append((si, sj))
    return False


def check_main():
    i, j, r = map(int, input().split())
    if i+j <= r: return False
    i, j = i-1, j-1
    check_diamond(i, j, r)
    return True

def check_diamond(ci, cj, cr):
    std_step = ((0,-1),(-1,0),(0,1),(1,0))
    std_didj = ((-1,1),(1,1),(1,-1),(-1,-1))
    for idx in range(4):
        k = 0
        si, sj = std_step[idx]
        i, j = ci+si*cr, cj+sj*cr
        di, dj = std_didj[idx]
        while k <= cr:
            check_diamond_unit(i, j)
            i, j, k = i+di, j+dj, k+1


def check_diamond_unit(i, j):
    global mat, I, J
    if not (0<=i<I and 0<=j<J): return
    mat[i][j] = '*'

# 입력
I, J = map(int, input().split())
N = int(input())
mat = [[0] * J for _ in range(I)]
ret = main()
print('YES' if ret else 'NO')
if ret: print(mat[I-1][J-1]-1)

BFS를 활용하여 해결할 수 있는 문제였다.

1. 가로 세로 입력을 받고, 2차원 배열 mat을 만든다.
2. mat에 차가 막히는 범위를 표시하고 BFS를 돌려 우측 하단의 좌표에 도달할 수 있는지 체크한다.
3. 특정 차의 범위 내에 (0,0) 좌표가 있다면 이동이 불가능하므로 이 경우 NO를 출력하도록 범위를 체크한다.
4. BFS에서는 가장자리에 차의 범위를 표시하게 된다. 내부는 3번의 과정을 통해 필터링할 수 있다.
5. 차의 중앙 좌표를 기준으로 거리만큼의 다이아몬드 영역을 모두 표시할 수 있다면 (0,0) 좌표부터 BFS를 실시한다.
6. 최하단에 도달하거나, 더 조회할 좌표가 없다면 종료한다.
7. 결과에 따라 목적 좌표의 값을 출력한다.

결과

맞았습니다!!