[Boj/백준] 22352 Python

문제출처: https://www.acmicpc.net/problem/22352

22352번: 항체 인식

 

 

1. 문제 접근 방식

처음 그래프를 순환하다가 다음 그래프와 다른 부분이 생기면 BFS를 사용한다.

BFS를 적용한 후에 그래프를 두 개 비교했을때 다른 부분이 있으면 NO를 둘이 같으면 YES를 출력한다.

이때 주의할 것이 BFS를 한번 사용하면 더이상 사용하지 못하고

BFS를 사용할 때 주변에 같은 원소가 있으면 모두 BFS가 적용되어야 한다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

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

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    k = 0
    k = graph[x][y]
    graph[x][y] = graph2[x][y]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx < 0 or ny < 0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny] == k:
                graph[nx][ny] = graph[x][y]
                queue.append((nx,ny))

n, m = map(int,sys.stdin.readline().split())

graph = []
graph2 = []

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

for i in range(n):
    graph2.append(list(map(int,sys.stdin.readline().split())))

flag = True
for i in range(n):
    for j in range(m):
        if graph[i][j] != graph2[i][j]:
            bfs(i,j)
            flag = False
    if flag==False:
        break

if graph == graph2:
    print('YES')
else:
    print('NO')

 

 

3. 결과 및 느낀점

난잡하게 풀었다...

처음에 틀렸었는데 테스트 케이스도 다 되고 반례를 생각해봤다.

1 1

1 2

2 1

1 2

이면 NO가 출력되어야 하는데 YES가 출력되는 반례를 찾았다.

그래서 BFS 함수 안에서 nxny가 처음 xy와 같으면 그것도 BFS를 적용시켜 해결했다.

이중 포문을 탈출하기 위해서

flag라는 변수를 사용했다.