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

문제

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

1012번: 유기농 배추

---

 

풀이

이 문제는 DFS/BFS 두 방법으로 풀 수 있다.

두 가지 방법 모두를 사용해서 풀어보았다.

문제는 DFS 같은 경우 RecursionError (재귀와 관련된 에러)가 발생한다.

 

RecursionError는 재귀의 깊이가 깊어졌을 때 발생한다.

 

백준에서는 재귀의 최대 깊이가 1000으로 설정되어 있기 때문에

재귀의 최대 깊이를 높여줘야 한다.

 

코드 내에 sys.setrecursionlimit(10000) 를 작성해주면 된다.

 

DFS

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10000)

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


def dfs(x, y):

    # 상하좌우 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (0 <= nx < N) and (0 <= ny < M):
            if graph[nx][ny] == 1:
                graph[nx][ny] = -1
                dfs(nx, ny)


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for _ in range(N)]
    cnt = 0

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

    for i in range(N):
        for j in range(M):
            if graph[i][j] > 0:
                cnt += 1
                dfs(i, j)

    print(cnt)

 

BFS

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    graph[i][j] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for _ in range(N)]
    cnt = 0

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

    for i in range(N):
        for j in range(M):
            if graph[i][j] > 0:
                cnt += 1
                bfs(i, j)

    print(cnt)