[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으로 바꿔준다는 개념을 사용하면 된다.
Author And Source
이 문제에 관하여([Python/Baekjoon] 1012. 유기농 배추), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jnl1128/PythonBaekjoon-1012.-유기농-배추저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)