[파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5)

[파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5)

15806번: 영우의 기숙사 청소

---

문제

---

풀이

0. 방향성 생각

• 그림2의 (a) (b)의 시작 곰팡이 위치를 보면 서로 교차해서 나타나는 것을 확인할 수 있다.
• 홀수일에 피는 곰팡이, 짝수초에 피는 곰팡이, 항상 피어있는 곰팡이로 구분한다.
• 예제 1번의 테케를 보면 곰팡이가 중앙에서 피어서 증식하지 못하는 경우도 생긴다.
• 입력에 추가하기 전, n = 1,2거나 n=3의 중심처럼 곰팡이가 증식하지 못하는 엣지케이스 잡아내기
•  

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m,k,day = map(int,input().split())
arr = [[[0]*4 for _ in range(n)] for _ in range(n)]

info,check = [],[]
for i in range(m+k):
    x,y = map(int,input().split())
    if i<m: info.append((x-1,y-1))
    else: check.append((x-1,y-1))

dire = [(2,1),(-2,1),(2,-1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
inside = lambda x,y : 0<=x<n and 0<=y<n

• 좌표가 1부터 시작하니까 0부터 시작하게 바꿔주기
• 8방향 정의하기
• arr[y][x][상태] = 시간 : (x,y)에 있는 곰팡이가 어떤 상태로 도달하기 위한 최소 시간 기록
• state = 1 : 곰팡이가 홀수초에 핀다, state = 2 : 곰팡이가 짝수초에 핀다, state = 3 : 곰팡이가 항상 피어있다.

2. 증식 가능한 곰팡이 구분

q = deque()
for x,y in info:
    remain = False
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if inside(nx,ny):
            remain = True
            break
    if remain:
        q.append((x,y,1))
        arr[y][x][1] = 1

• 8방향 중 하나라도 증식 가능하면 증식 가능한 곰팡이
• q에는 시작 시간 1부터 시작한다.
• arr[y][x][1] = 1 : 홀수초에 피는 곰팡이. 처음으로 갱신되는 시간 1

3. BFS

while q:
    x,y,t = q.popleft()
    for dx,dy in dire:
        nx,ny,nt = x+dx,y+dy,t+1
        if 0<=nx<n and 0<=ny<n:
            if not any(arr[ny][nx]):
                s = 1 if nt%2 else 2
                arr[ny][nx][s] = nt
                q.append((nx,ny,nt))
            elif (((arr[ny][nx][1] and not nt%2) or (arr[ny][nx][2] and nt%2))
                  and not arr[ny][nx][3]):
                arr[ny][nx][3] = nt
                q.append((nx,ny,nt))

• not any를 사용해서 처음으로 도달하는 노드에 현재 시간이 홀수인지, 짝수인지 구분하여 큐에 넣어줬다.
• 재방문하는 노드이고 곰팡이가 서로 반대 시간에 피고 (홀수날에 피는데 짝수날에 방문) 항상 피는 곰팡이 상태가 갱신되어있지 않으면 방문처리

4. 출력

nday = day+1
clean = False
for x,y in check:
    if ((0 < arr[y][x][3] <= nday) or
        ((0 < arr[y][x][1] <= nday) and (arr[y][x][1]%2 == nday%2)) or
        ((0 < arr[y][x][2] <= nday) and (arr[y][x][2]%2 == nday%2))):
        clean = True
        break
    
print('YES' if clean else 'NO')

• 검사날이랑 현재 상태를 비교해서 풀기
• nday의 짝 홀 유무에 따라서 범위 내에 있고, 피어있는 시기랑 nday 짝 홀이 맞으면 된다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m,k,day = map(int,input().split())
arr = [[[0]*4 for _ in range(n)] for _ in range(n)]

info,check = [],[]
for i in range(m+k):
    x,y = map(int,input().split())
    if i<m: info.append((x-1,y-1))
    else: check.append((x-1,y-1))

dire = [(2,1),(-2,1),(2,-1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
inside = lambda x,y : 0<=x<n and 0<=y<n

q = deque()
for x,y in info:
    remain = False
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if inside(nx,ny):
            remain = True
            break
    if remain:
        q.append((x,y,1))
        arr[y][x][1] = 1

while q:
    x,y,t = q.popleft()
    for dx,dy in dire:
        nx,ny,nt = x+dx,y+dy,t+1
        if 0<=nx<n and 0<=ny<n:
            if not any(arr[ny][nx]):
                s = 1 if nt%2 else 2
                arr[ny][nx][s] = nt
                q.append((nx,ny,nt))
            elif (((arr[ny][nx][1] and not nt%2) or (arr[ny][nx][2] and nt%2))
                  and not arr[ny][nx][3]):
                arr[ny][nx][3] = nt
                q.append((nx,ny,nt))

nday = day+1
clean = False
for x,y in check:
    if ((0 < arr[y][x][3] <= nday) or
        ((0 < arr[y][x][1] <= nday) and (arr[y][x][1]%2 == nday%2)) or
        ((0 < arr[y][x][2] <= nday) and (arr[y][x][2]%2 == nday%2))):
        clean = True
        break
    
print('YES' if clean else 'NO')

풀고보니까 arr[y][x][0]은 안썼는데 그냥 3개로 구분해도 될듯

코멘트

풀이 자체는 오래 걸리진 않는데 자꾸 하나씩 놓쳐서 삽질을 하게된다......

구상 먼저 하고 엣지케이스도 생각하기.

 

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m,k,day = map(int,input().split())
arr = [[0]*n for _ in range(n)]
info,check = [],[]
for i in range(m+k):
    x,y = map(int,input().split())
    if i<m: info.append((x-1,y-1))
    else: check.append((x-1,y-1))

inside = lambda x,y : 0<=x<n and 0<=y<n
dire = [(2,1),(-2,1),(2,-1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
q = deque()
for x,y in info:
    remain = False
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if inside(nx,ny):
            remain = True
            break
    if remain:
        q.append((x,y,1))
        arr[y][x] = 1

while q:
    x,y,t = q.popleft()
    
    for dx,dy in dire:
        nx,ny,nt = x+dx,y+dy,t+1
        if inside(nx,ny):
            if arr[ny][nx] == 0:
                s = 1 if nt%2 else 2
                arr[ny][nx] = s
                q.append((nx,ny,nt))
            elif ((arr[ny][nx] == 1 and not nt%2) or
                  (arr[ny][nx] == 2 and nt%2)):
                arr[ny][nx] = 3
                q.append((nx,ny,nt))

nday = 1 if (day+1)%2 else 0
clean = False
for x,y in check:
    if ((nday and (arr[y][x] == 1 or arr[y][x] == 3)) or
        (not nday and (arr[y][x] == 2 or arr[y][x] == 3))):
        clean = True
        break
    
print('YES' if clean else 'NO')

• 첫 코드는 이런식으로 풀었다.
• 단순히 어떤 노드에 방문했던 시간이 짝수인지 홀수인지 구분하는 경우로 풀었다.
• 테케도 다 맞아서 그냥 넘어갔는데 계속 틀리길래, 3x3 격자에서 어떤식으로 증식이 되나 확인했다.
• 단순히 방문노드가 짝 홀로 하는게 아니라 퍼지는 시간을 고려해서 기록해줘야했다.
• visit 안쓰고 풀 수 있을거같아서 그냥 풀었는데 엄청 삽질해버림