BOJ 16569 화산쇄설류(Python 3)

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

 t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다.

저 문장은 화산쇄설류가 1초마다 인접한 상하좌우로 퍼진다는 이야기이다.

BOJ에 나온 탈출,불,불!과 같은 유형의 BFS 문제이다.

먼저 화산쇄설류를 BFS로 돌리고, 그다음 재상이를 BFS로 돌리면 된다.

재상이가 화산은 지나 갈 수 없다는 사실에 유의하며 문제를 풀면 된다.

코드1은 BFS를 다 끝낸다음, 마지막에 완전 탐색으로 높이의 최대값과 그때의 시간을 구했고, 코드2는 현재 BFS 돌리는 좌표가 h에 저장된 값보다 높으면 h와 t를 바로바로 갱신할 수 있도록 만들었다.

코드1 확인

from collections import deque
n,m,v=map(int,input().split())
ax,ay=map(int,input().split())
q=deque([(ax-1,ay-1)])
Fq=deque()
D=[list(map(int,input().split())) for _ in range(n)]
S=[[-1]*m for _ in range(n)]
S[ax-1][ay-1]=0
dx,dy=[0,0,1,-1],[1,-1,0,0]
Max=500000
FS=[[Max]*m for _ in range(n)]
for _ in range(v):
    x,y,z=map(int,input().split())
    Fq.append((x-1,y-1,z))
    FS[x-1][y-1]=z
    S[x-1][y-1]=-2
while Fq:
    x,y,z=Fq.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m and FS[nx][ny]>t+1:
            Fq.append((nx,ny,z+1))
            FS[nx][ny]=z+1
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 S[nx][ny]==-1 and FS[nx][ny]>S[x][y]+1:
            q.append((nx,ny))
            S[nx][ny]=S[x][y]+1
h=0;t=0
for i in range(n):
    for j in range(m):
        if S[i][j]!=-1 and S[i][j]!=-2 and D[i][j]>h:
            h=D[i][j]
            t=S[i][j]
print(h,t)

코드2 확인

from collections import deque
n,m,v=map(int,input().split())
ax,ay=map(int,input().split())
q=deque([(ax-1,ay-1)])
Fq=deque()
D=[list(map(int,input().split())) for _ in range(n)]
S=[[-1]*m for _ in range(n)]
S[ax-1][ay-1]=0
dx,dy=[0,0,1,-1],[1,-1,0,0]
Max=500000
FS=[[Max]*m for _ in range(n)]
h,t=D[ax-1][ay-1],0
for _ in range(v):
    x,y,z=map(int,input().split())
    Fq.append((x-1,y-1,z))
    FS[x-1][y-1]=z
    S[x-1][y-1]=-2
while Fq:
    x,y,z=Fq.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m and FS[nx][ny]>z+1:
            Fq.append((nx,ny,z+1))
            FS[nx][ny]=z+1
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 S[nx][ny]==-1 and FS[nx][ny]>S[x][y]+1:
            q.append((nx,ny))
            S[nx][ny]=S[x][y]+1
            if D[nx][ny]>h:
                h=D[nx][ny]
                t=S[nx][ny]
print(h,t)