[백준][Python] 22352 항체 인식

그래프, bfs / 골드 5

💉

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

22352번: 항체 인식

 

 

내 풀이

 

from collections import deque

def bfs(x, y):
    global change

    q = deque()
    q.append((x,y))
    visited[x][y] = True

    current = after[x][y] # 현재 영역의 값
    if before[x][y] != current: # 백신을 놓기 전과 후의 결과가 다를 때
        change += 1

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and before[x][y] == before[nx][ny]: # 범위 내, 방문하지 않은 곳, 인접한 영역
                visited[nx][ny] = True
                if current != after[nx][ny]:
                    return 'NO'
                q.append((nx, ny))


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

before = [[] * M for _ in range(N)] # 백신을 놓기 전
after = [[] * M for _ in range(N)] # 백신을 놓은 뒤
visited = [[False] * M for _ in range(N)]
change = 0

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

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

ans = 0

for i in range(N):
    for j in range(M):
        if not visited[i][j]:
            if bfs(i, j) == 'NO':
                ans = 1
            
if ans == 1 or change > 1:
    print('NO')
else:
    print('YES')

 

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

ans: 촬영 대상이 맞은 백신이 CPCU-1202 백신일 수 있는지를 구분하는 변수 (0: YES, 1: NO)

 

격자 전체를 돌면서 아직 방문하지 않은 칸을 발견한 경우 bfs를 호출한다.

bfs 함수를 호출하면, 같은 값을 가지면서 상하좌우로 인접해 있는 영역을 검사 & 방문처리 하게 된다.

ans = 0

for i in range(N):
    for j in range(M):
        if not visited[i][j]:
            if bfs(i, j) == 'NO':
                ans = 1

 

ans가 1이거나(bfs에서 NO를 리턴한 경우) change가 1을 초과하는 경우, 결과는 NO이다.

백신을 놓으면 한 칸에만 항체가 생성되기 때문에, 한 영역이 아닌 여러 영역의 값이 변화한 경우도 배제해주어야 한다.

또한, 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있기 때문에 아예 변화가 일어나지 않은 경우(change = 0)도 있을 수 있다.

이때의 결과는 YES이다.

if ans == 1 or change > 1:
    print('NO')
else:
    print('YES')

 

 

✔️ bfs 함수

 

current에 현재 영역의 값을 저장한다.

백신을 놓기 전과 후의 결과가 다르다면, 항체가 변화한 것이므로 change를 증가시킨다.

current = after[x][y] # 현재 영역의 값
if before[x][y] != current: # 백신을 놓기 전과 후의 결과가 다를 때
    change += 1

 

현재 좌표의 상하좌우를 검사한다.

인접한 새 좌표가 범위 내에 있고, 아직 방문하지 않은 칸이며, 서로 같은 값을 가져야 하는 칸인 경우

방문 처리 후, 같은 값을 가지고 있는지 검사한다.

만약 서로의 값이 다르다면, 인접해 있는 칸들이 동일한 값으로 함께 변화한 것이 아니기 때문에 결과는 NO이다.

만약 같은 값을 가지고 있다면, 새 좌표를 q에 추가하여, 또 다른 인접한 칸들을 계속해서 검사해보아야 한다.

while q:
    cx, cy = q.popleft()

    for k in range(4):
        nx, ny = cx + dx[k], cy + dy[k]

        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and before[x][y] == before[nx][ny]: # 범위 내, 방문하지 않은 곳, 인접한 영역
            visited[nx][ny] = True
            if current != after[nx][ny]:
                return 'NO'
            q.append((nx, ny))