[BOJ/백준] 15806 영우의 기숙사 청소

# N: 방 크기
# M : 공팡이 개수
# K : 검사하는 개수
# t : 남은 일수
import sys

def input():
    return sys.stdin.readline().rstrip()
N,M,K,T = map(int,input().split())

mold = set()
visited = [[False]*N for _ in range(N)]
for _ in range(M):
    input_list = list(input().split())
    temp = []
    for check in input_list:
        if check.isdigit():
            temp.append(int(check))
    if len(temp)==2:
        mold.add((temp[0]-1,temp[1]-1))
        visited[temp[0]-1][temp[1]-1] = True
cleaning_place = []
for _ in range(K):
    input_list = list(input().split())
    temp = []
    for check in input_list:
        if check.isdigit():
            temp.append(int(check))
    if len(temp) == 2:
        cleaning_place.append((temp[0]-1,temp[1]-1))


dx = [-2,-1,1,2,2,1,-1,-2]
dy = [-1,-2,-2,-1,1,2,2,1]
time = 0
result = 'NO'
flag = False
while time <T:
    new_mold = set()
    for x,y, in mold:
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                visited[nx][ny] = True
                new_mold.add((nx,ny))
    time += 1
    cnt = 0
    for x,y in cleaning_place:
        if (x,y) in new_mold and (T-time)%2 == 0:
            result = 'YES'
            flag= True
            break
        elif (x,y) not in new_mold and visited[x][y]:
            cnt += 1
    else:
        if cnt == len(cleaning_place):
            flag = True
    if len(new_mold) == 0:
        flag = True
    mold = set(list(new_mold))
    if flag:
        break

print(result)

 

문제 자체는 그렇게 어렵지 않았지만, 문제가 되었던 것은 데이터 오류가 있었던 문제였다.

 

이 문제를 푸시는 분들은 수정이 되기전까지 청소할 곳이 주어지는 INPUT에 공백이 있으니, 그 점을 주의해서 풀기 바란다.

 

문제 아이디어 자체는 간단한 편이다.

 

청소를 해야하는 시간 T가 있으면, 그 시간 T의 짝수번째 시간전에 곰팡이가 존재하면, 시간 T일때에도

 

곰팡이가 존재한다는 점을 생각하면 된다.

 

그냥 전체시간 T에 대해서 반복을 하면 시간초과가 날 수 있다. 그렇기 때문에 매 시간마다 판별을 해주면 된다.

 

판별을 하는 방법은 다음과 같다. 현재 곰팡이가 존재하며, 청소시간 T와 현재시간 time의 차이가 2의배수이면,

 

해당 지역에는 곰팡이가 있는것이고, 청소를 해야한다. 그러므로 그때 break를 해주면 된다.

 

그리고 모든 경우에 대해서, 현재 곰팡이가 존재하지 않고, 곰팡이가 생겼던 적이 있는경우라면, 청소시간 T에

 

곰팡이가 존재하지 않는 것이기 때문에, 청소를 할 필요가 없다. 모든 청소구간에 대해서 이와 같은 경우가 생기면,

 

그 문제에서는 청소를 할 필요가 없기 때문에 반복문을 탈출시켜주면 된다.

 

 

import sys
from collections import deque

def grow(arr,queue):
    dx = [-2,-1,1,2,2,1,-1,-2]
    dy = [-1,-2,-2,-1,1,2,2,1]

    while queue:
        x,y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <=nx<N and 0<=ny<N:
                if arr[nx][ny] == -1:
                    arr[nx][ny] = arr[x][y] + 1
                    queue.append((nx,ny))


input = sys.stdin.readline


N,M,K,T = map(int,input().split())
mold_even = deque()
mold_odd = deque()
odd_list =[[-1]*N for _ in range(N)]
even_list = [[-1]*N for _ in range(N)]
for i in range(M):
    x,y = map(lambda x: x-1,map(int,input().split()))
    if (x+y)%2:
        odd_list[x][y] = 0
        mold_odd.append((x,y))
    else:
        even_list[x][y] = 0
        mold_even.append((x,y))



grow(even_list,mold_even)
grow(odd_list,mold_odd)
# 초기값이 홀수이면 odd에 있는데 이 경우, T가 짝수일때에만 ON이 된상태이다.
# odd_list : odd이면 T가 짝수이면 ON
# odd_list : odd이면 T가 홀수이면 off
# even_list : odd이면서 T가 짝수이면 off
# even_list : odd이면서 T가 홀수이면 ON
# 이렇게 되기 때문에 odd이면서 T가 짝수이면 odd_list를 odd이면서 T가 홀수이면 even_list를 탐색해줘야한다.
# even도 똑같이 해주면 된다.
for _ in range(K):
    x,y = map(lambda x: x-1,map(int,input().split()))
    flag = True
    if (x+y)%2 and T%2:
        flag = False
    elif (x+y)%2 == 0 and T%2==0:
        flag = False
    if flag and 0<=odd_list[x][y]<=T:
        print('YES')
        break
    elif not flag and 0<=even_list[x][y]<=T:
        print('YES')
        break
else:
    print('NO')

 

이 풀이는 jh05013님의 풀이를 분석해서 한 풀이이며, 좀 더 깔끔한 코드이고 배울게 많은 코드라서 공부를 한 풀이입니다.

 

이 풀이 같은 경우 처음 곰팡이의 위치를 홀수 짝수일때를 구분해서, 두 Array로 나누어서 저장을 시켜줍니다.

 

그 이유는 다음과 같습니다.

 

이 문제에서 곰팡이가 퍼지는 방식은 (+-2,+-1) or (+-1,+-2) 입니다.

 

그렇다보니 현재 위치가 짝수이면, 그 다음 위치는 홀수, 그 다음의 위치는 짝수이게 됩니다. 

 

그러면 처음위치가 짝수인 것은 0초에는 짝수 1초에는 홀수 2초에는 짝수 3초에는 홀수로 반복합니다.

 

이와 같이 홀수 인것은 0초에는 홀수 1초에는 짝수 2초에는 홀수가 됩니다.

 

 

이렇게 2개의 행렬로 나누고, bfs를 진행시켜줍니다.

 

 

인제 판별을 해줘야하는데 크게 4가지로 나뉩니다.

 

청소 위치가 짝수일때 홀수일때와 청소시간이 짝수 홀수 일때입니다.

	청소시간 짝수	청소시간 홀수
위치 짝수	even_list : 곰팡이가 생길수도 있다. odd_list : 곰팡이가 생길수가 없다.	even_list : 곰팡이가 생길수가 없다. odd_list : 곰팡이가 생길수가 있다.
위치 홀수	even_list : 곰팡이가 생길수가 없다. odd_list : 곰팡이가 생길수가 있다.	even_list : 곰팡이가 생길수도 있다. odd_list : 곰팡이가 생길수가 없다.

 

 

표를 나타내면 위와 같습니다. 시간이 짝수이면, EVEN_LIST는 짝수의 위치에 대해서만 곰팡이가 있습니다.

 

그에 반해 ODD_LIST는 홀수 위치에서 대해서만 곰팡이가 있습니다.

 

그와 반대로 시간이 홀수 이면 EVEN_LIST는 홀수위치에만 곰팡이가 존재할 수 있고,

 

ODD_LIST에는 짝수 위치에서만 곰팡이가 생길수 있습니다.

 

 

이렇듯 곰팡이가 짝수간격으로 패턴이 있고, 홀수일때와 짝수일때가 서로 반대되는 점을 응용하면

 

위와 같이 간단하게 구현할 수 있는 문제였습니다.