백준/ Gold 5 문제 , 백준 파이썬 22352 , 항체 인식 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 22352 , 항체 인식  [BFS]

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
그냥 두 리스트에서 다른 영역들이 존재할 때 단 한 번의 퍼트림만으로 서로 같아질 수 있냐 없냐를 판단하는 문제이다.

 

 

문제 출처

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

22352번: 항체 인식

 

 

 

풀이

 

1. 기본 세팅

 

1. 상하좌우 움직임

 

2. N,M 입력받기

 

3. S,P 두 리스트 입력받기

 

 

2. BFS

 

서로 다른 영역의 문자일때 S 쪽의 문자를 P쪽의 문자로 바꿔준다.

 

인접한 영역들로 퍼져나가면서 p 변수로 전달된 문자로 바꿔준다.

 

 

 

3. BFS 호출 및 처리

 

BFS는 단 한번만 호출할 수 있다.

 

왜냐하면 단 한번의 퍼짐만으로 서로 같아지는 지를 확인해야하기 때문.

 

이후 bfs 가 종료되면 check 변수를 통해 구별하여 for 문을 종료 시킨다.

 

이후 퍼짐이 진행 된 S가 P와 동일해졌는지 비교해보고 만약 다른 부분이 한곳이라도 존재한다면 NO 를 출력한 뒤 프로그램을 종료시킨다.

 

같다면 YES를 출력한다.

 

 

정답

 

 

from collections import deque
import sys
input=sys.stdin.readline

dr=[(1,0), (0,1), (-1,0), (0,-1)]

N,M=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(N)]
P=[list(map(int,input().split())) for _ in range(N)]

def bfs(s,p,x,y):
    dq=deque()
    dq.append([x,y])
    S[x][y]=p
    while dq:
        X,Y=dq.popleft()
        for a,b in dr:
            mx,my=X+a,Y+b
            if 0<=mx<N and 0<=my<M:
                if S[mx][my]==s :
                    S[mx][my]=p
                    dq.append([mx,my])
check=False   
for i in range(N):
    for j in range(M):
        if S[i][j]!=P[i][j]:
            bfs(S[i][j],P[i][j],i,j)
            check=True
            break
    if check==True:
        break
        
for i in range(N):
    for j in range(M):
        if S[i][j]!=P[i][j]:
            print('NO')
            exit(0)
            
print('YES')