BOJ 22352번: 항체 인식

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

22352번: 항체 인식

백신을 맞기 전(before)과 맞은 후(after)의 배열의 원소를 비교하다가 다른 원소가 나오는 경우에 해당 원소에 백신을 맞은 것으로 가정하고 백신을 맞아서 변화된 데이터는 after의 원소값이라 생각하고 dfs를 통해 해당 원소부터 상하좌우로 갈 수 있는 모든 before의 원소의 값을 바꾼다.

dfs를 실행한 후 다시 before와 after의 원소를 비교하고 만약 다른 값이 있다면 NO를 출력하고, 모두 같다면 YES를 출력한다.

애초에 before와 after의 값이 완전히 같은 경우도 YES를 출력하도록 처리해야 한다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
before = []
after = []
for _ in range(N):
    before.append(list(map(int, input().split())))
for _ in range(N):
    after.append(list(map(int, input().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visit = [[False]*M for _ in range(N)]
q = []

def dfs(a, b, old, new):
    q.append([a,b])
    before[a][b] = new
    visit[a][b] = True
    
    while(q):
        v = q.pop()
        for i in range(4):
            x = v[0]+dx[i]
            y = v[1]+dy[i]
            if (x>=0 and x<N and y>=0 and y<M and visit[x][y]==False and before[x][y]==old):
                visit[x][y] = True
                before[x][y] = new
                q.append([x,y])

    for i in range(N):
        for j in range(M):
            if (before[i][j]!=after[i][j]):
                print("NO")
                return
    print("YES")
    return

for i in range(N):
    for j in range(M):
        if (before[i][j]!=after[i][j]):
            dfs(i,j, before[i][j], after[i][j])
            sys.exit(0)
print("YES")

dfs를 실행할 위치를 고른 후 dfs를 실행하고, 다시 before와 after의 원소값이 같은 지 체크할 때 그 전에 탐색한 위치에서 이어서 탐색하면 된다고 생각하고 for i in range(이전위치, N): for j in range(이전위치, M) 으로 해놓는 멍청한 짓을.. 어차피 N,M<=30이므로 그냥 다시 처음부터 탐색하도록 했다..^^