[Python/Baekjoon] 1012. 유기농 배추

문제

1. 난이도: 백준 실버 2

2. 문제 요약

• 배추밭에서 배추가 모여 있는 곳에 지렁이 한 마리씩 사용한다고 한다.
• 입력:
  - 첫 번째 줄: 테스트 케이스의 개수
  - 각 테스트 케이스의 첫 번째 줄: 배추밭 가로의 길이, 세로의 길이, 배추의 총 개수
  - 다음 K 줄: 배추가 있는 위치(반복x)
• 출력: 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수

3. 문제 핵심: BFS/DFS

내 코드

1. BFS

def bfs(start, m , n):
    queue = deque()
    queue.append(start)
    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 graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    

from collections import deque
testCaseNum = int(input())
graph = []

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

for i in range(testCaseNum):
    answer = 0
    col, row, num = map(int, input().split(" "))
    graph=[[0]*col for _ in range(row)]
    for j in range(num):
        y,x = map(int, input().split(" "))
        graph[x][y] = 1
    for r in range(row):
        for c in range(col):
            if graph[r][c] == 1:
                answer +=1
                bfs((r,c), col, row)
    answerList.append(answer)

for i in answerList:
    print(i)
  

2. DFS

def dfs(x, y, n, m):
    graph[x][y] = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or nx>= m or ny<0 or ny>= n:
            continue
        if graph[nx][ny] == 1:
            dfs(nx, ny, n, m)



from collections import deque
import sys
sys.setrecursionlimit(10**7)
testCaseNum = int(input())
graph = []

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

for i in range(testCaseNum):
    answer = 0
    col, row, num = map(int, input().split(" "))
    graph=[[0]*col for _ in range(row)]
    for j in range(num):
        y,x = map(int, input().split(" "))
        graph[x][y] = 1
    for r in range(row):
        for c in range(col):
            if graph[r][c] == 1:
                answer +=1
                dfs(r, c, col , row)
    answerList.append(answer)

for i in answerList:
    print(i)

배운 점

• sys.setrecursionlimit(n): 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕다.
  - 파이썬으로 재귀함수 문제를 풀 때면 위 함수를 항상 사용하자.
• BFS문제에서 궁극적으로 모두 연결되는 경우는 +1을 해주면서 최단 거리를 구해가지만
• 연결되어 있지 않고 뭉터기씩 나뉘어 있는 경우는 돌면서 한 뭉터기를 1에서 0으로 바꿔준다는 개념을 사용하면 된다.