728x90
[백준] 1012번 - 유기농 배추
풀이 시간: 30분 이내
이 문제는 DFS, BFS 2가지 방식으로 모두 풀 수 있는 문제다.
최대 재귀한도 깊이 문제로 BFS로 풀이하는 것이 더 좋을 듯 하다.
(풀이1) BFS
1) 문제 해결 아이디어
2) 소스코드
from collections import deque
# 위치벡터(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS
def bfs(x, y):
# 시작 좌표 삽입, 방문처리
queue = deque()
queue.append((x, y))
graph[x][y] = 0
while queue:
x, y = queue.popleft()
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):
queue.append((nx, ny))
graph[nx][ny] = 0
t = int(input()) # 테스트 케이스 수
for _ in range(t):
# 가로, 세로, 배추 개수
m, n, k = map(int, input().split())
# 0: 땅, 1: 배추
graph = [[0] * m for _ in range(n)]
res = 0 # 지렁이 수
for i in range(k):
y, x = map(int, input().split())
graph[x][y] = 1 # 배추 표시
# 탐색
for i in range(n):
for j in range(m):
# 배추이면
if graph[i][j] == 1:
bfs(i, j)
res += 1 # 지렁이 개수 1증가
print(res)
(풀이1) BFS
1) 문제 해결 아이디어
2) 소스코드
import sys
sys.setrecursionlimit(10**6) # 최대 재귀 깊이 설정
t = int(input()) # 테스트 케이스 수
# 위치벡터(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# DFS
def dfs(x, y):
# 현재 좌표 방문 처리
graph[x][y] = 0
# 상하좌우 탐색
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):
dfs(nx, ny)
return 0
for _ in range(t):
# 가로, 세로, 배추 개수
m, n, k = map(int, input().split())
# 0: 땅, 1: 배추
graph = [[0] * m for _ in range(n)]
res = 0 # 지렁이 수
for i in range(k):
y, x = map(int, input().split())
graph[x][y] = 1 # 배추 표시
# 탐색
for i in range(n):
for j in range(m):
# 배추이면
if graph[i][j] == 1:
dfs(i, j)
res += 1 # 지렁이 개수 1증가
print(res)
첫번째 오류. 런타임 에러: RecursionError
이 에러는 최대 재귀한도 깊이 에러이다.
파이썬에서는 재귀의 한도가 정해져있는데,
<해결 방법>
1. 재귀 함수를 사용하지 않는 것
DFS대신 BFS로 구현하면 된다.
2. sys.setrecursionlimit() 사용
파이썬이 정한 최대 재귀 깊이를 변경해주는 것이다.
보통 sys.setrecursionlimit(10**6) 정도로 해주면 해결된다.
728x90
'[Python]알고리즘 > 백준' 카테고리의 다른 글
[DFS/BFS/완전탐색] ▲ 7576번 - 토마토(BFS) (0) | 2022.03.30 |
---|---|
[DFS/BFS/완전탐색] ▲ 2178번 - 미로 탐색 (0) | 2022.03.30 |
[DFS/BFS/완전탐색] 2667번 - 단지번호붙이기 (0) | 2022.03.30 |
[DFS/BFS/완전탐색] 2606번 - 바이러스 (0) | 2022.03.30 |
[DFS/BFS/완전탐색] 1260번 - DFS와 BFS (0) | 2022.03.30 |