[백준/BOJ] #22352 항체 인식.python(파이썬)

문제 링크 / 출처

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

22352번: 항체 인식

 

풀이

이 문제의 핵심은 같은 데이터 값을 가진 상하좌우로 인접한 모든 칸을 구하는 것이다.

 

while 문을 활용해,

 

1. 해당 좌표의 값을 after값으로 변경
2. 상하좌우 탐색하여 before데이터와 같은 값을 가진 좌표 저장
3. 저장한 좌표를 하나씩 꺼내와 해당 좌표로 이동

 

를 반복하여 계산하였다.

 

계산한 값을 통해 before행렬을 바로바로 변화시켰고, 최종적인 before행렬과 after행렬을 비교하였다.

 

코드

N, M = map(int, input().split())

before = [list(map(int, input().split())) for _ in range(N)]
after = [list(map(int, input().split())) for _ in range(N)]

if before == after:  # 변화가 없는 경우
    print('YES')

else:  
    for i in range(N):
        for j in range(M):
            if before[i][j] - after[i][j] != 0:
                x, y = i, j
                break
        if before[i][j] - after[i][j] != 0:
            break
    before_num = before[x][y] 
    after_num = after[x][y]

    lst = []
    i, j = x, y     # 가장 상단의 변화한 숫자의 좌표 

    while True:
        before[i][j] = after_num

        if i>0:     # 같은 값을 가진 인접 좌표를 저장
            if before[i-1][j] == before_num:
                lst.append((i-1,j))
        if j>0:
            if before[i][j-1] == before_num:
                lst.append((i,j-1))
        if i<N-1:
            if before[i+1][j] == before_num:
                lst.append((i+1,j))
        if j<M-1:
            if before[i][j+1] == before_num:
                lst.append((i,j+1))    

        if not lst: # 모든 좌표를 사용한경우 
            break   
        i,j = lst.pop() # 저장된 좌표를 꺼내옴

    if before == after: # 모든 격자의 변화와 인접격자의 변화가 일치하는 경우 
        print('YES')
    else:
        print('NO')