[백준] 1012번 파이썬 (유기농 배추)

우선 문제에서 준 예제는 다음과 같다. 이렇게 배추가 있을 때 지렁이가 5마리 있으면 된다.

---

DFS와 BFS가 등장하기 시작하는 문제다. (solved.ac class 순서 기준) 중요한 개념이므로 이해하고 넘어갈 필요가 있다. 잘 정리되어 있는 아래 글을 참고하면 좋을 것 같다.

https://yunyoung1819.tistory.com/86

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

---

DFS를 활용한 코드는 아래와 같다. 추가로 백준에서 재귀함수의 최대깊이는 1000으로 설정되어 있기에 이걸 10000으로 바꿔줘야 한다.

 

# DFS
import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline

t = int(input().rstrip())

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

def dfs(x, y):
    if (x <= -1 or x >= n or y <= -1 or y >= m):
        return False
    
    if lst[x][y] == 1:
        lst[x][y] = 0

        for i in range(4):
            dfs(x + dx[i], y + dy[i])

        return True
    return False

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

    lst = [[0]*m for i in range(n)]

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

    cnt = 0
    for i in range(n):
        for j in range(m):
            if dfs(i, j):
                cnt += 1

    print(cnt)

---

BFS를 활용한 코드는 아래와 같다.

# BFS
import sys
from collections import deque
input = sys.stdin.readline

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

t = int(input().rstrip())

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    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 lst[nx][ny] == 1:
                queue.append((nx, ny))
                lst[nx][ny] = 0

    return

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

    lst = [[0]*m for i in range(n)]

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

    cnt = 0
    for i in range(n):
        for j in range(m):
            if lst[i][j] == 1:
                bfs(i, j)
                cnt += 1

    print(cnt)

---

첫 번째 코드가 DFS(깊이 우선 탐색)인 이유는 dfs 재귀함수를 활용함으로써 하나의 배추 위치를 찾으면 우선 x축 방향으로 1이 안 나오는 지점까지 dfs 함수를 돌린다. 그리고 y축 방향으로 또 1이 안 나오는 지점까지 돌린다.

반면 두 번째 코드가 BFS(너비 우선 탐색)인 이유는 queue에 append시켜 popleft를 통해 하나씩 꺼내서 함수를 돌리는 방식인데 이 방법을 사용하면 하나의 배추 위치를 찾았을 때 우선 주위 네 방향에 대해서 함수를 적용하고 1이 나온 지점에 대해 또 주위 네 방향에 대해 함수를 적용하는 방법을 사용하고 있기 때문이다.