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

🥚문제

---

🥚입력/출력

---

🍳코드

# 유기농 배추
from collections import deque
import sys

# bfs
def bfs(matrix, x, y):
    queue = deque()
    queue.append((x, y)) # (x, y) 삽입
    matrix[x][y] = 0  # 방문 표시, 0으로 값 변경
    while queue:
        v = queue.popleft() # pop
        x = v[0] # x update
        y = v[1] # y update
        # 상하좌우 인접 노드 삽입
        movs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for mov in movs:
            nx = x + mov[0]
            ny = y + mov[1]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == 1:
                    queue.append((nx, ny))
                    matrix[nx][ny] = 0  # 방문 표시, 0으로 값 변경

# main
t = int(sys.stdin.readline())
while t > 0:
    # 입력
    m, n, k = map(int, sys.stdin.readline().split())
    matrix = [[0]*m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        matrix[y][x] = 1 # 배추가 심어져 있음
    # 배추가 심어진 영역 구하기
    count = 0 # 영역 수
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                count += 1
                bfs(matrix, i, j)
    print(count)
    t -= 1

---

🧂아이디어

• 시간초과 떴다가, append 뒤 바로 visit 표시 해줬더니 성공했다. (결국 첫 제출에서는 bfs 구현할 때 빈틈을 보였다는 것)

• matrix 내에서 상, 하, 좌, 우로 탐색하는 것이 포인트