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

백준 1012번

문제

배추흰지렁이는 배추를 해충으로부터 보호해준다.
지렁이는 위, 아래, 양옆으로 움직일 수 있고 움직일 수 있는 영역에는 해충이 없다.

배추가 심어진 영역은 1, 없는 영역은 0으로 표현한다.

한나는 배추밭에 배추를 듬성듬성 심었는데, 배추밭 전체를 보호하려면 지렁이가 몇마리 필요한지 구해보자.

어떻게 풀면 좋을까?

결국 다 찾아야 한다고 생각했다. 한 지점에서 위아래, 양옆 중에서 어느 한칸이 1이면 그곳으로 이동, 다시 거기서 또 위아래, 양옆을 확인해야 할 것이다.
확인하는 영역을 밭의 크기를 넘기지 않고, 0보다 작아지지 않으면 된다.

풀이

dfs

# 위 오른쪽 아래 왼쪽
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

case = int(input())

def dfs(bat, x, y, h, w):
    for i in range(4):
        moveX = dx[i] + x
        moveY = dy[i] + y
        if 0 <= moveX < h and 0 <= moveY < w:
            if bat[moveX][moveY] == 1:
                bat[moveX][moveY] = 0
                dfs(bat, moveX, moveY, h, w)

def solution():
    for c in range(case):
        h, w, k = map(int, input().split())
        count = 0
        bat = [[0] * w for _ in range(h)]
        for i in range(k):
            x, y = map(int, input().split())
            bat[x][y] = 1
            print(bat)

        for x in range(h):
            for y in range(w):
                if bat[x][y] == 1:
                    dfs(bat, x, y, h, w)
                    count += 1
        print(count)

bfs

from collections import deque
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

case = int(input())

def bfs(bat, x, y, h, w):
    queue = deque()
    queue.append((x, y))
    bat[x][y] = 0
    while queue:
        curX, curY = queue.popleft()
        for i in range(4):
            moveX = dx[i] + curX
            moveY = dy[i] + curY
            if 0 <= moveX < h and 0 <= moveY < w:
                if bat[moveX][moveY] == 1:
                    bat[moveX][moveY] = 0
                    queue.append((moveX, moveY))

def solution():
    for c in range(case):
        h, w, k = map(int, input().split())
        count = 0
        bat = [[0] * w for _ in range(h)]
        for i in range(k):
            x, y = map(int, input().split())
            bat[x][y] = 1
            print(bat)

        for x in range(h):
            for y in range(w):
                if bat[x][y] == 1:
                    bfs(bat, x, y, h, w)
                    count += 1
        print(count)