BOJ 1012번: 유기농 배추

특이한 점은 없는 탐색 문제다.

오랜만에 푸는 탐색 문제다 보니 DFS 코드를 어떻게 구현할지 고민을 많이 했었는데, 그래도 감을 더듬어가며 코드를 짜니 금방 풀렸다.

 

[정답 코드 - Python]

T = int(input())

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def DFS(row, col, visited):
    for i in range(4):
        new_row = row + dy[i]
        new_col = col + dx[i]
        if field[new_row][new_col] == 1 and visited[new_row][new_col] == False:
            visited[new_row][new_col] = True
            DFS(new_row, new_col, visited)


for _ in range(T):
    M, N, K = map(int, input().split())
    field = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    visited = [[False for _ in range(M + 1)] for _ in range(N + 1)]
    cnt = 0

    for i in range(K):
        x, y = map(int, input().split())
        field[y][x] = 1

    for col in range(M):
        for row in range(N):
            if field[row][col] == 1 and visited[row][col] == False:
                cnt += 1
                DFS(row, col, visited)

    print(cnt)

반성

-> 다만 이 코드는 재귀적으로 깊이 탐색을 수행하는데, 파이썬의 최대 재귀 깊이는 생각보다 적다. (약 999)

파이썬으로 문제를 풀 때는 재귀를 최소화하도록 노력하자. (다만 문제 봐서 이렇게 야매 DFS로 풀 수 있으면 푸는것도.. ~__~)

 

-> DFS의 정석은 스택을 사용해 while stack != empty 동안, 탐색 결과를 스택에 저장하며 탐색하는 코드가 베스트라고 생각한다.

가능하면 이론을 코드에 반영할 수 있도록 해보자. (핑계를 대자면 풀 때 생각이 안났다..)