[알고리즘 문제 풀이][DFS] 백준 1012번 - 유기농 배추
백준 1012번 유기농 배추입니다.
(삼성 SW 코딩 테스트 유형 - DFS)
- 문제 설명: https://www.acmicpc.net/problem/1012
- 문제 풀이:
본 문제는 기업 코딩 테스트 유형에서 많이 보이는 가벼운 함정이 있으므로, 문제 풀이를 보기 전에 먼저 문제를 풀어볼 것을 추천드립니다.
아래와 같은 배추밭이 있을 때, 배추 (1) 가 연속된 곳에는 지렁이를 하나만 두면 됩니다. 그래서 아래 예시의 경우, 뭉쳐있는 1이 5군데가 있으므로 5마리의 지렁이가 필요하게 됩니다.
1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
연속된 배추를 구해야하기 때문에 본 문제는 DFS 로 풀이하면 됩니다. 왼쪽 위에서부터 탐색을 하면서 가장 먼저 나타나는 1에서부터 상하좌우로 연결된 것들은 재귀로 다 찾아다니는 것입니다. 그리고 더 이상 연결된 1이 없으면 재귀를 탈출하고 다시 다음 자리에서부터 연결된 1들을 탐색을 시작합니다.
본 문제에서 가장 큰 함정은 여타 다른 일반 DFS 문제와는 달리 x와 y가 반대로 들어온다는 것입니다!!!! 이 부분에 많은 분들이 런타임 에러를 겪기도 합니다. 실제 시험을 볼 때, 이런 실수를 일으키기 위해 함정을 넣기도 하는데 이것을 항상 주의하면서 문제를 푸시면 됩니다.
헷갈리지 않으려면 x와 x의 범위 M이 항상 같은 위치에 있도록 하면 됩니다. 예를 들어, x의 범위는 0에서 M 까지이고, y의 범위가 0에서 N 까지일 때, 2차원 배열의 a[x][y] 순으로 하기로 하였다면 for i in range(M): for j in range(N): a[i][j] 순으로 탐색하도록 순서만 맞춰주면 되는 것입니다.
※ 모든 점을 시작점으로 하면서 해당 점에서부터 BFS를 돌도록 하면 동일하게 BFS 로도 구현할 수 있습니다. (아래 코드의 findvege 라는 dfs 함수를 bfs 함수로 대체 가능)
- 코드:
import sys
sys.setrecursionlimit(10**6)
# dfs
def findvege(i, j):
# 상하좌우
for nx, ny in ((i-1, j), (i, j-1), (i+1, j), (i, j+1)):
if 0 <= nx < M and 0 <= ny < N and bat[nx][ny] == 1:
bat[nx][ny] = 0
findvege(nx, ny)
# input
for testcase in range(int(input())):
ans = 0
M, N, K = map(int, input().split())
bat = [[0]*N for _ in range(M)]
for row in range(K):
x, y = map(int, input().split())
bat[x][y] = 1
# main
for i in range(M):
for j in range(N):
if bat[i][j] == 1:
ans += 1
bat[i][j] = 0
findvege(i, j)
print(ans)코드는 다른 DFS, BFS 문제에 비해 짧은 편입니다.
- 실수 포인트 & 반례:
1. 런타임 에러
- x와 y 인덱스를 헷갈려서 순서를 섞어서 쓰는 경우 런타임 에러가 발생합니다. 순서가 잘 맞춰져 있는지 확인해야합니다.
질문 답변 예시: https://www.acmicpc.net/board/view/76229 및 https://www.acmicpc.net/board/view/76116
2. Python 런타임 에러
- recursion 깊이가 너무 적게 지정이 된 경우, 재귀를 하다가 런타임 에러가 발생할 수 있습니다. 코드 상단에 아래의 내용을 추가해주시면 됩니다. (파이썬의 기본 재귀 깊이 제한은 1000 정도)
import sys
sys.setrecursionlimit(10**6)https://www.acmicpc.net/board/view/37591
https://www.acmicpc.net/board/view/73928
3. 초기화 관련 런타임 에러, 메모리 에러, 틀렸습니다
본 문제는 다른 백준 문제들과 달리 test case 가 있기 때문에 매 test case 마다 배열 등의 정보를 초기화를 잘 해주어야합니다.
질문 답변 예시: https://www.acmicpc.net/board/view/74859 및 https://www.acmicpc.net/board/view/75243
4. 그 외 반례 모음
https://www.acmicpc.net/board/view/72617
입력)
1
3 2 4
1 0
0 1
1 1
2 1
정답)
1
입력)
1
3 3 6
2 0
0 1
2 1
0 2
1 2
2 2
정답)
1https://www.acmicpc.net/board/view/72241
입력)
2
2 2 2
0 1
1 0
2 2 2
0 1
1 0
정답)
2
2https://www.acmicpc.net/board/view/73639
입력)
1
2 3 5
0 0
0 1
0 2
1 0
1 1
정답)
1https://www.acmicpc.net/board/view/73723
입력)
1
2 2 2
0 1
1 0
정답)
2
입력)
1
2 2 3
0 0
1 0
0 1
정답)
1https://www.acmicpc.net/board/view/75578
입력)
1
3 2 5
0 0
0 1
1 1
2 1
2 0
정답)
1https://www.acmicpc.net/board/view/76256
입력)
1
2 2 3
0 0
1 1
0 1
정답)
1
https://www.acmicpc.net/board/view/73329
입력)
2
50 50 1
49 49
50 50 1
0 0
정답)
1
1