[Baekjoon] 1012. 유기농 배추

🔗 Problem Link

1012번: 유기농 배추

---

❔Thinking

• 배추밭과 배추의 위치가 주어질 때, 배추를 보호하는 최소한의 배추흰지렁이 수를 반환한다.
• 배추흰지렁이는 인접한 모든 배추를 보호할 수 있다.

---

💻Solution

import sys
from collections import deque
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1, 1]
T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    # 배추밭 생성
    graph = [[0] * M for _ in range(N)]
    # 배추밭 배추 심기
    for _ in range(K):
        y, x = map(int, input().split())
        graph[x][y] = 1
    # bfs정의
    def bfs(x, y):
        q = deque([(x, y)])
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M and graph[nx][ny] == 1:
                    graph[nx][ny] = 2
                    q.append((nx, ny))
    # 배추흰지렁이 풀기
    cnt = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

---

🗝️keypoint

1. 배추가 심어진 위치 주위에 모든 배추 위치를 파악하는 bfs 알고리즘을 활용할 수 있다.
2. bfs에서 해당 위치의 방문처리는, 큐에 append하면서 진행해야 중복 방문을 막을 수 있다.
   • (0,0) (0,1) (1,0) (1,1) 각 위치에 배추가 있을 때 popleft 후에 방문처리를 한다면 (1,0) (1,1)는 다시 방문해야 한다.