DFS에 대한 이해 - 유기농 배추 문제

1012번 - 유기농 배추

https://www.acmicpc.net/problem/1012

왜 DFS?

문제의 핵심은 “연결된 배추 그룹”을 찾는 것이다. DFS를 사용하는 이유는 이러한 연결된 그룹을 효율적으로 찾기 위함이다.

#dfs 함수
def dfs(x, y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return
    if array[y][x] == 1:
        array[y][x] = 0  # 방문 표시
        # 상하좌우 인접한 배추 탐색
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)

3 x 3 배추밭을 예시로 들어보자.

1 1 0
0 1 0
0 0 1

시작 위치 (0,0)에서 배추를 발견했다. array[0][0] 방문 표시를 위해 0으로 변환한다.

0 1 0
0 1 0
0 0 1

방문 표시 후 탐색 과정은 다음과 같다.

인접 위치 확인

1. 왼쪽(x-1): 없음
2. 오른쪽(x+1): 배추 발견 -> array[1][0] 방문 표시
3. 위쪽(y+1): 없음
4. 아래쪽(y-1): 없음

배추를 발견한 다음 위치 (0,1)에서

0 1 0
0 1 0
0 0 1

인접 위치 확인

1. 왼쪽(x-1): 없음
2. 오른쪽(x+1): 없음
3. 위쪽(y+1): 없음
4. 아래쪽(y-1): 배추 발견 -> array[1][1] 방문 표시

다음 위치 (1,1)에서

0 0 0
0 1 0
0 0 1

인접 위치 확인

1. 왼쪽(x-1): 없음
2. 오른쪽(x+1): 없음
3. 위쪽(y+1): 없음
4. 아래쪽(y-1): 없음

0 0 0
0 0 0
0 0 1

(1,1)의 위치에서 더이상 탐색할 배추가 없으므로 모든 재귀 과정을 종료하고 함수를 반환한다.

이로써 하나의 그룹 탐색이 완료된 것이다.

결론

이처럼 DFS는 그래프에서 연결된 모든 노드를 효율적으로 탐색할 수 있고, 그래프의 연결 요소를 찾는 것에 효과적이다.