[백준][Python] 22352번 항체 인식 - 골드 5

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

22352번: 항체 인식

문제

풀이

1. BFS알고리즘을 사용해서 문제를 풀어주기로 했습니다.

 

2. 우선 완전탐색을 통해서 백신을 놓기 전의 격자와 백신을 놓은 후의 격자를 비교해줍니다.

3. 만일 다른 데이터 값을 가진 격자 위치를 찾게 되면 그 격자 위치를 중심으로 백신을 놓기 전의 격자 위에 백신을 놓은 후의 격자의 데이터 값으로 수정하는 BFS탐색을 진행해줍니다.

 

4. 만일 정상적으로 수정이 되었다면 두 격자를 완전 탐색으로 동일한지 확인해줍니다.

 

코드

# 22352번 항체 인식
from collections import deque
import sys

input = sys.stdin.readline

dxys = ((1,0),(-1,0),(0,1),(0,-1))

m, n = map(int, input().split())
grid_before = [input().split() for _ in range(m)]
grid_after = [input().split() for _ in range(m)]

def bfs(sx, sy, new_num):
    queue = deque([[sx,sy]])
    visited = [[False]*n for _ in range(m)] 
    visited[sy][sx] = True
    target = grid_before[sy][sx]
    while queue:
        cx, cy = queue.pop()
        grid_before[cy][cx] = new_num
        for dx, dy in dxys:
            nx = cx + dx
            ny = cy + dy
            if 0 <= nx < n and 0 <= ny < m and visited[ny][nx] == False:
                if grid_before[ny][nx] == target:
                    queue.appendleft([nx, ny])
                    visited[ny][nx] = True

def checkAll():
    for i in range(m):
        for j in range(n):
            if grid_after[i][j] == grid_before[i][j]:
                continue
            else:
                return False
    return True


def solve():
    for i in range(m):
        for j in range(n):
            if grid_before[i][j] != grid_after[i][j]:
                bfs(j,i,grid_after[i][j])
                if checkAll():
                    return "YES"
                else:
                    return "NO"
    return "YES"

print(solve())

 

출력결과