백준_22352_항체 인식(python)

● 접근법

 - 처음에 격자 그림이 주어지고 항체가 상하좌우로 퍼진다는 조건을 보고 bfs를 떠올렸다. N,M의 크기가 크지 않은 것을 보고 bfs 확신이 생겼다.

● 풀이법

 ★ 두개 before에서 상하좌우로 마주친 칸이 같은 크기였다면 항체는 무조건 퍼져야 한다. ★

 

1. 그래프를 순차적으로 하나하나 탐색하면서 방문하지 않은 좌표를 check()함수를 이용해 확인한다.

2. beforeNumber와 afterNumber의 값이 다르다면 answer + 1해준다. (answer의 크기가 1 보다 커진다면 만들어질 수 없는 그래프이다. 왜냐하면 항체는 한 번만 뿌리기 때문이다.)

3. 상하좌우를 탐색하면서 그래프 안에 있으면서 before 그래프에서 서로 크기가 같은 것만 확인한다. (이 문제의 key는 before 그래프에서 서로 크기 같았던 것만 보는 것이다. 이렇게 하지 않고도 풀 수 있지만 그렇게 한다면 탐색 if 조건 분기점이 많아지게 된다.)

4.  처음에 들어온 afternumber와 after[nx][ny]가 같으면서 방문하지 않았다면 큐에 추가하고 방문처리하고 다음으로 넘어간다.

5. 큐에서 꺼낸 after[x][y] 와 after[nx][ny] 다르다면 바로 탐색을 끝내버린다. 맨 위에 별 표시를 해놨듯 무조건 퍼져야 하는데 안 퍼졌기에 더 이상 볼 것도 없게 answer를 크게 증가시켜 실행을 끝낸다.

● 코드

from collections import deque

n,m = map(int,input().split())
before = [list(map(int,input().split())) for i in range(n)]
after = [list(map(int,input().split())) for i in range(n)]
visited = [[0] * m for i in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def check(i,j,afterNumber,beforeNumber):
    global answer
    q = deque()
    q.append((i,j))
    visited[i][j] = 1
    if afterNumber != beforeNumber: # 값이 달라졌어 그러면 값을 하나 증가시켜
        answer += 1
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m and before[x][y] == before[nx][ny]: # 애초부터 이 값인 것만 들여보낸다.
                if after[nx][ny] == afterNumber and visited[nx][ny] == 0:
                    visited[nx][ny] = 1 # 방문처리를 해준다.
                    q.append((nx,ny)) # 큐에 nx,ny를 추가한다.    
                if  after[x][y] != after[nx][ny]:
                    answer += 100 # 끝내라는 의미이다 더 이상 볼게 없다.
                    return

answer = 0
flag = 0
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0: # 그냥 방문한 적 없으면 다 확인해야한다.
            check(i,j,after[i][j],before[i][j]) 
        if answer > 1: # 1 이상이면 더 이상 볼 것도 없으니까
            flag = 1
            break
    if flag == 1:
        break

if answer > 1:
    print("NO")
else:
    print("YES")

● 회고

오랜만에 재밌는 문제를 만났는데 틀려버려 너무 아쉽다...... 풀이에서 별표 쳐놓은 부분을 반례를 보고 깨달았다. bfs 문제를 선호하기도 하고 일반적인 단순 bfs만 구현하는게 아니였어서 신났던 것 같다. 덤벙됐다기에는 실수도 실력이라는 말이 있으니 다음에 틀리지 않게 집중해야겠다. 왜 생각하지 못했을까?........ 흠.... 생각을 해봤는데 문제에서 주어진 예제 입력만 보고 문제를 판단하려고 했기에 이런 오류가 난 것 같다. 문제가 이해되지 않는 수준이 아니라면 예시만 보고 판단하지 말아야겠다.