문제
접근
2차원 공간에서 영역의 개수를 찾는 문제이다.
배추가 심어져 있는 1의 칸 중에 방문하지 않은 칸에 대하여 BFS를 수행한다.
BFS를 수행한 횟수가 영역의 개수이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys
from collections import deque
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def bfs(i, j):
q = deque()
q.append((i,j))
visit[i][j] = 1
while q:
by, bx = q.popleft()
for x, y in zip(dx, dy):
nx = bx + x
ny = by + y
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if board[ny][nx] == 1 and visit[ny][nx] == 0:
visit[ny][nx] = 1
q.append((ny,nx))
#sys.stdin.readline().split()
T = int(input())
for _ in range(T):
m, n, k = map(int, input().split(' '))
board = [[0]*m for _ in range(n)]
visit = [[0]*m for _ in range(n)]
ans = 0
for i in range(k):
x, y = map(int, sys.stdin.readline().split(' '))
board[y][x] = 1
for i in range(n):
for j in range(m):
if board[i][j] == 1 and visit[i][j] == 0:
bfs(i, j)
ans += 1
print(ans)