[실버 3] 백준 1012 - 유기농 배추 (파이썬)

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

풀이

• M x N 밭에 K개의 배추가 심어져 있다.
• 상하좌우로 인접한 배추는 하나의 그룹으로 간주한다.
• 이 그룹 수 = 필요한 지렁이 수
• 목표: 테스트 케이스마다 그룹 수 출력

field = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]

field[y][x] 는 배추가 있는 위치를 표시하고, visited 이미 방문한 곳은 다시 탐색하지 않도록 체크한다.

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

상, 하, 좌, 우로 이동 할 수 있는 트릭을 작성한다.

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[y][x] = True

큐를 이용해서 너비 우선 탐색을 진행하고, 배추가 있고, 방문하지 않은 인접한 칸을 계속 탐색한다.

for y in range(N):
    for x in range(M):
        if field[y][x] == 1 and not visited[y][x]:
            bfs(x, y)
            count += 1

모든 칸을 돌면서 아직 방문하지 않은 배추칸에서 BFS를 시작한다.

한번 BFS를 수행할 때마다 그룹 하나를 완탐한다.

코드

# 백준 1012 - 유기농 배추
# 분류 : BFS

from collections import deque

T = int(input())
for _ in range(T) :
    M, N, K = map(int, input().split())

    
    field = [[0] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]

    for _ in range(K) :
        x, y = map(int, input().split())
        field[y][x] = 1

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

    def bfs(x, y) :
        queue = deque()
        queue.append((x, y))
        visited[y][x] = True

        while queue : 
            cx, cy = queue.popleft()
            for i in range(4) :
                nx, ny = cx + dx[i], cy + dy[i]
                if 0 <= nx < M and 0 <= ny < N :
                    if field[ny][nx] == 1 and not visited[ny][nx] :
                        visited[ny][nx] = True
                        queue.append((nx, ny))

    count = 0
    for y in range(N) :
        for x in range(M) :
            if field[y][x] == 1 and not visited[y][x] :
                bfs(x, y)
                count += 1
    
    print(count)