[Python][BOJ 22352] 항체 인식

[BOJ 22352] 항체 인식 Python 풀이

📌 문제 분석

• N×M 크기의 배열에서 백신 투여 전과 후의 상태가 주어짐
• 백신은 한 번만 투여되며, 투여된 칸과 상하좌우로 연결된 같은 값을 가진 칸들이 모두 동일한 값으로 변경됨
• 주어진 투여 후 상태가 가능한 결과인지 판단해야 함

🚨 시행착오

• 처음에는 모든 칸에서 DFS를 시작하고, 가능한 모든 값으로 변경해보는 방식으로 접근
• 시간 복잡도가 O(NM * NM * KNM)로 매우 높았음
• 실제로는 백신이 한 번만 투여된다는 점을 활용하여 최적화 가능했음

처음 코드의 문제점

• 불필요하게 모든 칸에서 DFS 시작
• 가능한 모든 값을 시도
• 매번 배열을 원상복구하는 연산 필요

어떻게 고쳤나요?

• 투여 전/후가 다른 첫 지점만 찾아서 DFS 실행
• 해당 영역을 투여 후의 값으로 한 번에 변경
• 전체 배열 비교로 가능 여부 판단

💡 해결 방안

import sys

def dfs(i,j,check):
    if check[i][j] == 1:
        return

    check[i][j] = 1

    di = [0,0,1,-1]
    dj = [1,-1,0,0]
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni and ni < N and 0 <= nj and nj < M and before[ni][nj] == before[i][j] and check[ni][nj] == 0:
            dfs(ni,nj,check)   

N,M = map(int,sys.stdin.readline().split())
before = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
after = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

found = False
for i in range(N):
    for j in range(M):
        if before[i][j] != after[i][j]:
            check = [[0 for _ in range(M)] for _ in range(N)]
            dfs(i, j, check)
            target_value = after[i][j]

            for ni in range(N):
                for nj in range(M):
                    if check[ni][nj] == 1:
                        before[ni][nj] = target_value
            found = True
            break
    if found:
        break

print("YES" if before == after else "NO")

🎯 이 문제의 핵심 포인트

1. 백신은 단 한 번만 투여된다는 점을 활용
2. DFS로 연결된 같은 값을 가진 영역을 찾기
3. 시간복잡도를 O(N*M)으로 최적화
4. 파이썬의 2차원 리스트 비교 연산자(==) 활용

✨ 이번 문제를 통해 배운 점

1. 문제 조건을 잘 활용하면 시간복잡도를 크게 줄일 수 있다
2. 모든 경우를 시도하기 전에 최적화 가능성을 검토해야 한다
3. 파이썬의 리스트 비교 연산자는 재귀적으로 모든 요소를 비교한다

🔍 코드 설명

• dfs 함수는 연결된 같은 값을 가진 영역을 체크
• 처음으로 다른 값을 가진 칸을 찾아 그 영역만 변경
• 최종적으로 전체 배열이 같은지 비교하여 가능 여부 판단
• 시간복잡도가 O(N*M)으로, N,M ≤ 30 이므로 충분히 빠르게 동작