[백준] 1012번: 유기농 배추 - Python

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

1012번: 유기농 배추

아이디어

• 가로 새로 크기만큼 배열 생성
• 입력된 좌표를 1로 변경
• 이중 for문을 돌며 1인 좌표에서 bfs 탐색 진행
• 탐색을 마친 좌표는 0으로 변경

from collections import deque
import sys

input = sys.stdin.readline

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

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if v[nx][ny] == 1:
                v[nx][ny] = 0
                queue.append((nx, ny))
    return

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    v = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        v[x][y] = 1

    for a in range(n):
        for b in range(m):
            if v[a][b] == 1:
                bfs(v, a, b)
                cnt += 1
    print(cnt)

마무리

• 모든 bfs문제에서 방문처리 배열을 만들지 않고 본 배열에서 처리하는 스킬이 필요했던 것 같음
• 그 외는 여러 bfs문제와 동일하게 진행