[알고리즘 문제 풀이][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
정답)
1

https://www.acmicpc.net/board/view/72241

입력)
2
2 2 2
0 1
1 0
2 2 2
0 1
1 0

정답)
2
2

https://www.acmicpc.net/board/view/73639

 

 

입력)
1
2 3 5
0 0
0 1
0 2
1 0
1 1

정답)
1

https://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

정답)
1

https://www.acmicpc.net/board/view/75578

입력)
1
3 2 5
0 0
0 1
1 1
2 1
2 0

정답)
1

https://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