[BOJ/백준] 백준 22352 항체인식 파이썬

문제 링크 : https://www.acmicpc.net/problem/22352

22352번: 항체 인식

결과 값이 다른 한칸에서 bfs 돌려서 값을 업데이트 해주고 비교해주면 되는 간단한 bfs 문제이다.

처음에는 모든 칸에서 bfs를 돌렸다.

 

값이 다른 구역은 한번만 나와야하니 bfs 돌리기 전에 값이 다른 구역이 두번 나온지 체크하고 두번이면 no 출력하고

bfs 돌리다가 두 구역의 모양이 다르면 no 출력하는 방식으로 했다.

모든칸 체크 소스

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())

board1 = [list(input().strip().split()) for _ in range(n)]
board2 = [list(input().strip().split()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

def solv():
    flag = True
    for x in range(n):
        for y in range(m):
            if not visited[x][y]:
                if board1[x][y] != board2[x][y]:
                    if flag:
                        flag = False
                    else:
                        return 'NO'
                if not bfs(x,y):
                    return 'NO'
    return 'YES'

def bfs(sx,sy):
    global visited
    q = deque([(sx,sy)])
    visited[sx][sy] = True
    target1 = board1[sx][sy]
    target2 = board2[sx][sy]

    while q:
        x,y = q.pop()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny,target1):
                if board2[nx][ny] != target2:
                    return False
                visited[nx][ny] = True
                q.appendleft((nx,ny))
    return True
def point_validator(x,y,target):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    elif visited[x][y]:
        return False
    elif board1[x][y] != target:
        return False
    return True
print(solv())

 

근데 생각해보니 굳이 다 돌 필요가 없었다.

어차피 값이 다른 구역은 많아야 한번만 나오니까 값이 다른 칸에 들어오면 bfs 돌려서 원래 구역을 결과값 칸 구역의 값으로 업데이트하고 전체 비교를 하면 끝이었다.

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())

board1 = [list(input().strip().split()) for _ in range(n)]
board2 = [list(input().strip().split()) for _ in range(n)]

def solv():
    for x in range(n):
        for y in range(m):
            if board1[x][y] != board2[x][y]:
                bfs(x,y)
                return check_ans()
    return 'YES'

def bfs(sx,sy):
    global board1
    visited = [[False] * m for _ in range(n)]
    q = deque([(sx,sy)])

    visited[sx][sy] = True
    target = board1[sx][sy]
    num = board2[sx][sy]
    while q:
        x,y = q.pop()
        board1[x][y] = num

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny,visited,target):
                visited[nx][ny] = True
                q.appendleft((nx,ny))

def check_ans():
    for x in range(n):
        for y in range(m):
            if board1[x][y] != board2[x][y]:
                return 'NO'
    return 'YES'
def point_validator(x,y,visited,target):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    elif visited[x][y]:
        return False
    elif board1[x][y] != target:
        return False
    return True
print(solv())