[BOJ] #1012_유기농 배추(Python3, 파이썬)

본 게시글은 백준 저지 알고리즘 문제를 '파이썬, Python3' 언어로 풀이한 내용을 주관적으로 정리하였으며, 내용과 관련된 코드리뷰 및 피드백 환영합니다.

티어

Silver II

문제 출처

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

 

---

풀이

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

T = int(input())

# 상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(graph, a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return


for _ in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    graph = [[0] * N for _ in range(M)]

    for _ in range(K):
        x, y = map(int, input().split())
        graph[x][y] = 1
    
    for i in range(M):
        for j in range(N):
            if graph[i][j] == 1:
                bfs(graph, i, j)
                cnt += 1
    
    print(cnt)

BFS 문제로 해결하였다. 가까운 곳부터 탐색해야하는 문제들은 BFS문제로 해결하면 좋다.
처음 그래프의 칸을 탐색하며 1인 칸을 발견하면 BFS를 수행하고, 1인 칸을 0으로 바꾸면 그 탐색을 모두 끝낼 경우 그 구역은 모두 1이 0으로 바뀐다. 
1인 칸을 발견해 BFS를 수행하고 카운트 + 1을 하면 정답을 구할 수 있다.