https://www.acmicpc.net/problem/15806
공부 날짜 : 2023.02.13
정답 참조 여부 : X
곰팡이가 매일 특정 규칙에 의해서 번식한다.
t일 후에 특정 위치를 구했을 때 해당위치에 곰팡이가 있는지 여부를 구하는 문제이다.
구현 공부를 위해서 고른 문제인데 bfs였던 문제.
처음에는 곰팡이 위치를 기준으로 곰팡이를 t번 번식 시켜주며 결과에 대해서 check_point를 순회하며 정답여부를 판단했다.
결과는 당연히 시간초과, 이 경우 O(N^2 * t)로 최대 3억번의 연산이 나온다.
그래서 다른 방법을 생각했는데
곰팡이는 2일 간격으로 계속해서 생성과 소멸을 반복한다.
무슨 말이냐면
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
1 0 0 0 1
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
이렇게 번식이된 후에는 다시 자기 위치로 번식되어 돌아온다는 소리이다.
굉장히 비슷한 유형이 있었는데 숨바꼭질 5가 상당히 비슷했다. (풀이)
숨바꼭질 5를 풀어본 방법으로 홀수, 짝수 최단거리를 구해서 저장하고 t가 홀수냐 짝수냐에 따라서 그에 해당하는 최단거리가 t보다 작냐로 결과를 판단했다.
시간초과까진 문제가 있음을 이해했는데, 로직을 찾고 구현한 뒤에 틀렸습니다가 나와서 굉장히 화가 났다. 맞왜틀만 계속 반복하다가 변수가 헷갈렸음을 알았다.......
청소 검사 날짜는 t일 후인데 계속 k일 후라고 체크하고 있었다......
다행히 문제는 잘 해결했지만 진짜 사소한 문제로 좀 답답했던 문제
소스코드
import sys
from collections import deque
input = sys.stdin.readline
###############################################
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]
###############################################
n, m, k, t = map(int, input().split())
# bfs를 위한 deque구조
mold = deque()
# 값 입력받기
for _ in range(m):
mold.append(tuple(map(int, input().split())))
# 좌표가 1,1부터 시작하므로 n+1까지 선언
# 해당 위치에 도달하는데 불가능한 경우는
# t일 이후에 도달한다는 의미로 max(t)+1로 초기화
# 한 위치에서 번식이 되었으면, 2일 간격으로 생성되거나 사라진다.
# 그래서 홀수 최단거리, 짝수 최단거리를 구한다.
room = [[[10001 for _ in range(n+1)] for _ in range(n+1)] for _ in range(2)]
# x,y에 거리 0을 추가해서 저장
# 초기 곰팡이는 1일후 어차피 모두 사라지므로 초기화 x
# 2일차때 초기 위치로 돌아오는 곰팡이만 계속 반복해서 생성되고 사라짐
for i in range(m):
x, y = mold[i]
mold[i] = (x, y, 0)
# 청소 검사날 체크하는 위치 리스트
check_area = [list(map(int, input().split())) for _ in range(k)]
# 탐색 가능한 모든 위치 탐색
while mold:
# 위치와 거리
x, y, dis = mold.popleft()
if dis >= 10001:
break
# 8가지 방향에 대해서
for dir in range(8):
nx = x + dx[dir]
ny = y + dy[dir]
# 범위 벗어나면 체크 안하는데 1~n까지가 범위이므로
# 부등호 잘 체크
if nx <= 0 or nx > n or ny <= 0 or ny > n:
continue
# 해당영역에 짝수번째, 홀수번째 일째에서 이전에 도달 했는지 체크하기
if room[(dis + 1) % 2][nx][ny] == 10001:
room[(dis + 1) % 2][nx][ny] = dis + 1
mold.append((nx, ny, dis + 1,))
check_clean = False
# 탐색이 완료된 뒤에
for x, y in check_area:
# t가 짝수냐 홀수냐에 따라 해당위치에 t일째 이전에 도달되면
# 청소 해야됨
if room[t % 2][x][y] <= t:
check_clean = True
break
if check_clean:
print("YES")
else:
print("NO")
