[python] 백준 - 22352 항체 인식

오늘은 백준 사이트의

항체 인식 문제에 대해서 풀어보려 한다.

 

문제에 관련된 정보는

아래 링크를 통해 확인할 수 있으며,

바로 오늘의 문제에 대해 이야기해보겠다.

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

22352번: 항체 인식

1. 아이디어 구현

 

나의 경우

이 문제는 dfs(깊이 우선 탐색)를 통해

문제를 해결하였다.

 

항체가 생겼다면

항체가 생긴 지점을 기준으로

붙어있는 같은 숫자들이

모두 항체와 같은 숫자로 변경된다는 점을 통해

 

항체가 생기기 이전과 이후를 비교해

달라지는 지점을 확인하여

주변을 전부 항체로 물들인 후

 

다시 한번 항체로 물든 시점과 결과(위의 이후)를 비교해

다른 점이 있다면

"NO"를

아니라면

"YES"를

출력했다.

 

2. 코드 구현

import sys
def change(r, c, virus, vaccine):
 
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    raw_data[r][c] = vaccine
    s = [(r, c)]
    while s:
        r, c = s.pop()
        for di in range(4):
            nr = r + dr[di]
            nc = c + dc[di]
            if 0 > nr or nr >= N or 0 > nc or nc >= M:
                continue
            if raw_data[nr][nc] == virus:
                raw_data[nr][nc] = vaccine
                s.append((nr, nc))
                
    for i in range(N):
        for j in range(M):
            if raw_data[i][j] != result_data[i][j]:
                return 'NO'
    
    return 'YES'
 
N, M = map(int, sys.stdin.readline().split())
 
raw_data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result_data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
 
ans = 'YES'
stop = False
 
for i in range(N):
    for j in range(M):
        if raw_data[i][j] != result_data[i][j]:
            ans = change(i, j, raw_data[i][j],result_data[i][j])
            stop = True
            break
    if stop:
        break
 
print(ans)