22352번 - 항체 인식

그래프가 두 개 주어집니다 (항체를 놓기 전, 항체를 놓은 후)
저희는 이 두 개의 그래프를 보고 놓은 항체가 CPCU-1202 백신인지 아닌지를 판별하면 됩니다.

CPCU-1202는 투약하면 현재 속해있는 값과 같은 데이터값을 가지고 상하좌우에 해당 값이 있을 경우, 그 칸으로 퍼져나갑니다. 그리고 최종적으로 더 퍼져나갈 공간이 없다면 특정한 값으로 업데이트됩니다.

---

입력

N,M = map(int,input().split())
before = []
after = []
que = deque()

먼저 입력을 받아주겠습니다.
항체 투약전 before, 항체 투약 후 after 그래프로 입력받겠습니다.

for _ in range(N):
    before.append(list(map(int,input().split())))
for _ in range(N):
    after.append(list(map(int,input().split())))

반복해서 총 두 번 받아줍니다.

---

로직

제가 생각한 해당 문제의 로직은 이렇습니다.
일단 항체를 투약하기 전과 투약한 후의 그래프에서 변화한 구간을 찾습니다.
그리고 해당 인덱스를 도출해서 투약한 후의 해당 인덱스를 투약 전의 해당 인덱스에 대입하고
둘이 비교해서 그래프가 일치하면 CPCU-1202, 아니라면 다른 항체가 투입된 겁니다.

changed = []
loaded = False
for i in range(N):
    for j in range(M):
        if before[i][j] != after[i][j]:
           if after[i][j] not in changed:

따라서 투약 전과 투약 후의 변화한 구간을 찾고 만약 변화한 구간 탐색을 안갔으면

                loaded = True
                before_changed = before[i][j]
                changed.append(after[i][j])
                bfs(i,j)
                break

변화한 구간에서 바뀌기 전 value는 before_changed에, 바뀐 후의 value는 changed에 넣고 해당 인덱스를 BFS 탐색하겠습니다.

    if loaded:
        break

loaded로 True/False 체크를 안해주게 되면 한 번만 돌아도 되는 BFS 탐색을 두 번 세 번 돌아 값이 오염될 수 있습니다.

---

탐색

기준점은 before 그래프입니다.
위에 말씀드렸다시피

after 그래프의 변화된 구간의 value를 before 그래프의 변화된 구간에 대입한 값
<=>
after 그래프

와 비교했을 때 일치해야 CPCU-1202를 투약했다고 볼 수 있기 때문입니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

BFS 사용을 위해 상하좌우 설정과 que를 불러와주고

def bfs(x,y):
    global before_changed
    boolean = False
    que.append([x,y])

que에 추가하면서 탐색을 시작합니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue

항상 하는 4방향 탐색을 실시해주되

            if before[nx][ny] == before_changed:
                boolean = True
                before[nx][ny] = changed[0]
                que.append([nx,ny])

만약 탐색구간이 변화된 구간이라면 after 그래프에서 변화된 값을 before 그래프의 변화구간에 대입해주도록 합시다. 그리고 해당 구간은 que에 추가시켜서 주변 탐색을 재실시합니다.

    if boolean == False:
        before[x][y] = changed[0]

추가적으로 탐색이 아예 실행되지 않았다면 항체가 퍼질 공간이 존재하지 않았다는 의미이므로 해당 위치만 변화된 값을 대입해주도록 합시다.

---

출력

if before == after:
    print('YES')
else:
    print('NO')

마지막으로 그래프가 일치하면 YES, 아니라면 NO를 출력시키면 해결할 수 있습니다.

---