백준 1012번 <유기농 배추>

백준 알고리즘 1012번

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

1012번: 유기농 배추

---

1012번

농약을 쓰지 않고 배추를 재배할 때 중요한 것은 배추를 해충으로부터 보호하는 것이다. 해충 방지에 효과적인 배추흰지렁이는 배추 근처에서 서식하며 해충을 잡아먹는다. 또한 옆 배추로도 옮겨가며 해충을 잡아먹는다. 배추가 심어져있는 위치가 주어질 때 모든 배추가 해충 방지하기 위해서 배추흰지렁이는 몇 마리가 필요한지 구하여라.

 

입력으로 첫 줄에는 테스트케이스의 수 testcase가 들어온다. 두 번째 줄부터 각 테스트케이스에 대해 첫 줄에는 배추밭의 가로길이 M과 세로 길이 N 그리고 배추가 심어져있는 위치의 개수 K가 주어진다. 그 다음 K줄에 배추의 위치가 주어진다.

 

출력으로는 각 테스트케이스에 대해 배추흰지렁이가 최소 몇 마리 필요한지 구해서 출력하면 된다.

---

문제 해결

이 문제는 bfs로 해결할 수 있는 문제이다.

인접 노드를 해당 위치의 상, 하, 좌, 우로 생각하여 문제를 풀면 된다.

 

또한 배추가 심어져있지 않은 곳(=0)은 bfs를 수행할 필요가 없다는 것을 기억해야 한다.

 

이중 for문을 이용하여 배추밭을 순서대로 가면서 방문하지 않았고 배추가 심어져있을 경우에 bfs를 수행하고 bfs를 수행한 횟수를 정답으로 출력하면 된다. 

(bfs를 수행할 경우 해당 인덱스와 인접한 배추가 심어져있는 곳은 모두 방문처리가 되므로 나중에 for문에서 bfs를 다시 수행하지 않게 된다.)

---

코드

from collections import deque


def bfs(b, a):
    queue = deque()
    queue.append((b,a))
    visit[b][a] = True
    aL = [1, 0, -1, 0]
    bL = [0, 1, 0, -1]
    while queue:
        tb, ta = queue.popleft()
        for i in range(4):
            taL = ta + aL[i]
            tbL = tb + bL[i]
            if taL < 0 or tbL < 0 or taL >= m or tbL >= n:
                continue
            if not visit[tbL][taL] and graph[tbL][taL] == 1:
                queue.append((tbL, taL))
                visit[tbL][taL] = True



testcase = int(input())

for _ in range(testcase):
    m,n,k = map(int, input().split())

    graph = [[0 for _ in range(m)] for _ in range(n)]
    visit = [[True for _ in range(m)] for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1
        visit[b][a] = False


    result = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and not visit[i][j]:
                bfs(i, j)
                result += 1
    print(result)

---

결과

---