코테준비/백준

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

예찬예찬 2023. 8. 14. 10:58
728x90
반응형

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

아이디어

  • 가로 새로 크기만큼 배열 생성
  • 입력된 좌표를 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문제와 동일하게 진행
728x90
반응형