🪴 Quartz 4.0

BOJ 1012 - 유기농 배추

2 min read

풀이

“단지번호붙이기” 문제와 유사한 문제이다.

이어져 있는 정점들을 하나의 그룹으로 묶어서 몇개의 그룹이 필요한 지 알아내는 문제이다.

2중 반복문을 통해 2차원 배열을 탐색하는 중 1이 발견될 시 BFS 를 통해 인접하는 모든 1들을 방문처리 해준 뒤 ans 를 1 더해준다.

이를 2차원배열의 끝까지 반복하면 총 몇개의 그룹이 생성되었는지 ans 출력을 통해 알 수 있다.

소스코드

# 유기농 배추
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(graph, i, j):
    q = deque()
    q.append([i, j])
    graph[i][j] = 0  # 시작 점 방문처리
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m:  # 범위 내일 때
                if graph[nx][ny] == 1:  # 집이 이어져 있을 경우
                    q.append([nx, ny])
                    graph[nx][ny] = 0  # 방문 처리
    return
 
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
for t in range(int(input())):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    ans = 0
 
    for p in range(k):
        y, x = map(int, input().split())
        graph[x][y] = 1
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(graph, i, j)
                ans += 1
    
    print(ans)

References

Graph View