[BOJ 27211, Python] 도넛 행성 풀이

import sys
from collections import deque
input = sys.stdin.readline

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

matrix = []

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

for _ in range(n):
    matrix.append(list(map(int,input().split())))

count = 0

def bfs(sx,sy):
    queue = deque()
    queue.append((sx,sy))
    matrix[sy][sx] = 1
    while queue:
        nx,ny = queue.popleft()
        for i in range(4):
            tx,ty = nx+dx[i], ny+dy[i]
            if(tx == -1):
                tx = m - 1
            elif (tx == m):
                tx = 0
            
            if(ty == -1):
                ty = n - 1
            elif (ty == n):
                ty = 0

            if(matrix[ty][tx] == 0):
                queue.append((tx,ty))
                matrix[ty][tx] = 1

for y in range(n):
    for x in range(m):
        if (matrix[y][x] == 0):
            bfs(x,y)
            count += 1

print(count)

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

10026번: 적록색약

적록색약과 거의 비슷한 문제이다.

 

주의점은 영역이 도넛 형태로 되어있어서 (토러스) 상하좌우로 계속 이동해도 면을 벗어나지 않는 다는 점이다.

 

기존의 BFS를 작성하는 코드에서

1. 영역이 벗어나는 에러 케이스를 잡는 부분을 버리고,

2. 벗어날 시 위치를 이동시켜주는 코드를 추가해준 뒤

3. 모든 영역을 돌면서 비어 있는 공간마다 BFS를 적용시키면 된다. (돌때마다 카운트를 세주는건 덤)