[bfs/백준] 1012번 : 유기농 배추

- 문제 : https://www.acmicpc.net/problem/1012

 

문제 이해

- 2차 행렬에서 1로만 이루어진 영역의 개수를 세는 문제다. 

- 영역의 개수를 세기 위해 bfs를 이용하면 된다.

- 탐색을 위한 조건으로는 (방문하지 않은 노드) + (기존 행렬 값 == 1)이어야 한다. 

- 그 외에는 일반 bfs 함수로 진행하면 된다. 

 

정답 풀이 

import sys
input = sys.stdin.readline

def bfs(x, y, visit):
    queue = [[x, y]]
    visit[x][y] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visit[nx][ny] and matrix[nx][ny] == 1:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
        
    
for _ in range(int(input())):
    m, n, k = map(int, input().split())
    matrix = [[0] * n for _ in range(m)]
    for _ in range(k):
        a, b = map(int, input().split())
        matrix[a][b] = 1
        
    visit = [[0] * n for _ in range(m)]  
    answer = 0 
    for i in range(m):
        for j in range(n):
            if not visit[i][j] and matrix[i][j] == 1:
                answer += 1
                bfs(i, j, visit)
                
    print(answer)