[백준 25552 🥇] 잔디 예측하기

 

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

25552번: 잔디 예측하기

문제 풀이

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().strip().split(' '))
present=[list(sys.stdin.readline().strip()) for _ in range(n)]
d=int(sys.stdin.readline())
future=[list(sys.stdin.readline().strip()) for _ in range(n)]

# future를 기준으로 기존의 present에 도달할 수 있는지 확인
queue=deque()
visited=[[0]*m for _ in range(n)]

def bfs_weed():
    global queue, visited, future
    while queue:
        y,x=queue.popleft()
        for dy in range(y-d, y+d+1):
            for dx in range(x-d, x+d+1):
                if 0 <= dy < n and 0 <= dx < m and visited[dy][dx] == 0 and future[dy][dx] == 'O' and abs(y-dy)+abs(x-dx)<=d:
                    queue.append((dy, dx))
                    visited[dy][dx] = 1

for i in range(n):
    for j in range(m):
        if present[i][j]=='O' and visited[i][j]==0:
            queue.append((i,j))
            visited[i][j]=1
            bfs_weed()

for i in range(n):
    for j in range(m):
        if (future[i][j]=='O' and visited[i][j]==0) or (future[i][j]=='X' and present[i][j]=='O'):
            print('NO')
            sys.exit(0)

print('YES')

• 문제 풀이 아이디어가 중요했다!
• 우선 기존 잔디 상태에서 예측 잔디 상태로 도달할 수 없는 경우는 두 가지로 나눌 수 있다.
• 첫 번째로, 예측 잔디 상태가 X인데, 기존 잔디 상태가 O인 경우는 불가능하다. 왜냐하면 기존에 있던 잔디가 사라질 수는 없기 때문이다.
• 두 번째로, 기존 잔디 상태가 O인 위치에서(즉,잔디가 위치하는 곳)에서 상하좌우로 D 내로 움직일 수 위치(예측 잔디 배열의 위치가 O이어야 함)를 BFS를 통해서 모두 탐색한 결과인 Visited 배열에서 예측 잔디에선 잔디가 있다고 표시되어 있지만, Visited 배열은 0인, 즉 도달할 수 없는 위치에 잔디가 있다고 예측하는 경우이다. 
• 여기서 중요한 점은 상하좌우로 D 내로 움직일 수 있는 위치를 정의하는 것인데, 현재 위치 y,x를 기준으로 (y-d~y+d, x-d~x+d)를 탐색하면서 현재 위치 y에서 움직일 위치 dy의 차이인 abs(y-dy)와 현재 위치 x에서 움직일 위치 dx의 차이인 abs(x-dx)의 합이 d이하여야 한다.