[Algorithm] 백준 22352번 : 항체 인식

문제

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

22352번: 항체 인식

 

풀이코드 (Python)

from collections import deque

n, m = map(int,input().split()) 

input_arr = [0]*n

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

output_arr = [0]*n

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

dx=[0,0,-1,1] #상하좌우
dy=[-1,1,0,0]
     
def bfs(sx,sy):
    global input_arr
    visited = [[False] * m for _ in range(n)]	 # 방문처리 배열만들기
    q = deque([(sx,sy)])	# deque를 이용하여 queue 만들기

    visited[sx][sy] = True  # 일단 처음은 방문 처리
    target = input_arr[sx][sy]	# 타깃이 되는 값
    num = output_arr[sx][sy]	# 바뀔 값
    
    while q:	# queue에 원소가 다 빠질때까지 반복
        x,y = q.popleft()	# 첫번째 원소 꺼내기
        input_arr[x][y] = num

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if check(nx,ny,visited,target):
                visited[nx][ny] = True
                q.append((nx,ny))

def check(x, y, visited, target):
  if x < 0 or y < 0 or x >= n or y >= m:
        return False
  elif visited[x][y]:
      return False
  elif input_arr[x][y] != target:
      return False
  return True
  
              
def final_check():
  for x in range(n):
    for y in range(m):
      if input_arr[x][y] != output_arr[x][y]:
        return 'NO'
  return 'YES'

def solv():
  for x in range(n):
    for y in range(m):
      if input_arr[x][y] != output_arr[x][y]:
        bfs(x, y)
        return final_check()
  return 'YES'

print(solv())

 

풀이설명

BFS를 이용하면 되는 문제!

일단 input과 output의 배열 중 다른 값을 가지는 좌표를 구하고, 어차피 항체는 하나니까 굳이 모든 구역을 다 돌지 않고 한번 다르게 나온 값이 있는 구역에서 BFS를 통해 상하좌우를 탐색하고 input배열의 타겟 요소를 같은 위치에 있는 output배열의 요소 값으로 바꿔주면 된다.

즉, BFS로 값을 비교하고 업데이트 시켜주고 마지막에 다시한번 더 확인하는 것

 

 

---

Reference

• 백준 22352
• https://westmino.tistory.com/6