☁️ [백준/Python] 2012번 유기농 배추 (BFS, DFS)

Dior·2022년 11월 8일

[백준/Python]

목록 보기

2/2

Problem

지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

Input

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

Output

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

🙄 Approach

0으로 채워진 2차원 리스트 맵을 구현한 다음, 배추가 있는 위치를 1로 바꾼다.
그 다음 맵의 처음부터 마지막까지 반복하면서 중간에 배추를 발견하면
지렁이의 숫자를 증가시키고 인접한 배추를 포함해서 위치의 값을 0으로 바꾼다.
인접한 위치 방문? => BFS 또는 DFS를 사용.

그런데 굳이 전체 맵을 반복해야 할까?
맵을 만들지 않고 배추가 있는 위치만을 기억하고 방문할 때마다 없앤다.
배추 위치 리스트를 다 없앤다면 조사는 끝

⭐️ BFS 풀이

BFS(Breadth First Search) 너비 우선 탐색
FIFO(FIrst In First Out)를 위해 자료구조 Queue를 사용한다.
Python에서는 collentions의 deque로 구현

🤔 왜 list가 아닌 deque를 사용하는가?

답은 deque가 더 빠르다.
Queue 자료구조 구현 시, deque는 시간복잡도 O(1), list는 시간복잡도 O(n)이다.

간단하게 설명하자면
deque는 linked list로 맨 앞의 값을 제거하더라도 재할당이 일어나지 않는다.
반면에 list는 index를 재할당 해줘야 한다.

따라서 deque는 list[i]와 같은 index 접근이 불가능하다.

✔ Code

import sys
from collections import deque

T = int(sys.stdin.readline())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    cabbage = [ list(map(int, sys.stdin.readline().split())) for _ in range(K)]
    
    queue = deque()
    
    while cabbage:
        earthworm_count += 1
        queue.append(cabbage.pop(0))
        
        while queue:
            target = queue.popleft()
            tx, ty = target[0], target[1]
            
            for i in range(4):
                x = tx + dx[i]
                y = ty + dy[i]
                
                if x < 0 or x >= M or y < 0 or y >= N:
                    continue
            
                else:
                    if [x, y] in cabbage:
                        queue.append([x, y])
                        cabbage.remove([x, y])
                        
                    else:
                        continue
        
    print(earthworm_count)

⭐️ DFS 풀이 - 재귀

DFS(Depth First Search) 깊이 우선 탐색
재귀함수로 구현

코드 제출 시 런타임 에러 (RecursionError)로 통과하지 못했다.
이유는 아래 인용으로 설명한다.

RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.

BOJ의 채점 서버에서 이 값은 1,000으로 되어 있습니다.

sys.setrecursionlimit()을 사용하는 것입니다. 이 함수를 사용하면, Python이 정한 최대 재귀 갚이를 변경할 수 있습니다. 최대 재귀 깊이를 1,000,000 정도로 크게 설정하면 런타임 에러 없이 실행이 됩니다.

✔ Code

# 유기농 배추
import sys
sys.setrecursionlimit(10**6)
    
T = int(sys.stdin.readline())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def DFS(target):
    tx, ty = target[0], target[1]
        
    for i in range(4):
        x = tx + dx[i]
        y = ty + dy[i]
        
        if x < 0 or x >= M or y < 0 or y >= N:
            continue
        
        else:
            if [x, y] in cabbage:
                cabbage.remove([x, y])
                DFS([x, y])
                
            else:
                continue

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    cabbage = [ list(map(int, sys.stdin.readline().split())) for _ in range(K)]
    earthworm_count = 0

    while cabbage:
        earthworm_count += 1
        target = cabbage.pop(0)
        
        DFS(target)
                    
    print(earthworm_count)

⭐️ DFS 풀이 - Stack

DFS(Depth First Search) 깊이 우선 탐색
LIFO(Last In FIrst Out)를 위해 자료구조 Stack을 사용한다.
Stack을 List로 구현

✔ Code

import sys
    
T = int(sys.stdin.readline())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    cabbage = [ list(map(int, sys.stdin.readline().split())) for _ in range(K)]
    earthworm_count = 0
    stack = []
    
    while cabbage:
        earthworm_count += 1
        stack.append(cabbage.pop(0))
        
        while stack:
            target = stack.pop(-1)
            tx, ty = target[0], target[1]
            
            for i in range(4):
                x = tx + dx[i]
                y = ty + dy[i]
                
                if x < 0 or x >= M or y < 0 or y >= N:
                    continue
                else:
                    if [x, y] in cabbage:
                        stack.append([x, y])
                        cabbage.remove([x, y])
                    else:
                        continue
    
    print(earthworm_count)