[Algorithm] 백준 1012번: 유기농 배추 | BFS, 스택으로 구현한 DFS, for ~ else문

문제 출처: https://www.acmicpc.net/problem/1012

---

1. 결과

1) BFS 이용: 메모리 32124KB, 시간 104ms

2) 스택으로 구현한 DFS 이용: 메모리 29452KB, 시간 88ms

2. 풀이

이 문제는 비교적 평범한 DFS 문제라고 생각한다. 전체 좌표를 탐색하다가 만약 1(배추가 심어진 곳)을 발견하면 이와 상, 하, 좌, 우로 연결된 모든 배추 좌표를 방문하고, 이 전체를 배추흰지렁이 한 마리로 해결할 수 있다. 즉, 방문한 적이 없는 1을 발견하면 필요한 배추흰지렁이의 수를 1만큼 추가하고, 값을 1을 가지면서 해당 위치와 상, 하, 좌, 우로 연쇄적으로 연결된 모든 좌표들을 방문한 상태로 바꾸면 된다. 하지만 이를 재귀로 구현한 DFS를 이용하면 재귀 오류가 발생한다. 나는 이 부분에서 재귀를 이용한 DFS는 안된다고 생각하고, BFS 또는 스택으로 구현한 DFS를 이용했다. 다른 풀이를 보고 알았지만 sys.setrecursionlimit()를 이용해서 재귀로 구현한 DFS 풀이도 가능하다.

아래의 코드에는 일단 내가 직접 작성한 BFS, DFS(스택으로 구현) 코드가 있다. 여기서 BFS는 덱(deque)을 이용했고, DFS에는 스택을 이용했다. 그리고 추가로 DFS에서는 for ~ else문을 이용했다. deque나 BFS, DFS는 다른 문제에서 다룬 적이 있지만, for ~ else문을 직접 이용해본 적은 이 코드가 처음이다. 우선, for ~ else문은 for문을 통해 정해진 루프를 돌게 한다. 그리고 이 for문 안에서 특정 조건을 만족하면 for문을 멈추도록 break를 넣어준다. else는 이 for문에서 break가 발생한 적이 없을 경우, 발생하는 명령을 나타낸다. 즉, for문에서 break가 발생했는가의 여부를 알 수 있다. 아래 코드에서는 현재 위치에서 더 이상 방문하지 않은 1이 없다면 else문을 통해 현재 위치를 스택에서 제거되도록 설계했다. 아무래도 최적, 최소가 아닌 특정 위치에서 끝까지 모두 방문하는 방식으로 푸는 문제였기 때문에 BFS보다는 DFS가 더 메모리와 시간 측면에서 효율적이었다.

import sys
from collections import deque

# BFS 이용 - 32124KB, 104ms
def bfs(board, visited, n, m, position):
    q = deque([position])
    dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while q:
        y, x = q.popleft()
        if 0 <= y < n and 0 <= x < m and board[y][x] and not visited[y][x]: visited[y][x] = True
        for dy, dx in dr:
            i, j = y+dy, x+dx
            if 0 <= i < n and 0 <= j < m and board[i][j] and not visited[i][j]:
                visited[i][j] = True
                q.append([i, j])

# DFS 이용(스택으로 구현. 재귀로 구현하면 재귀 제한 오류 발생) - 29452KB, 88ms
def dfsByStack(board, visited, n, m, position):
    stack = [position]
    dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while stack:
        cur_i, cur_j = stack[-1]
        visited[cur_i][cur_j] = True
        for di, dj in dr:
            i, j = cur_i+di, cur_j+dj
            if 0 <= i < n and 0 <= j < m and board[i][j] and not visited[i][j]:
                stack.append((i, j))
                break
        else: stack.pop()

T = int(sys.stdin.readline())
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    ones = [[0] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]
    cnt = 0
    
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        ones[y][x] = 1
    
    for i in range(N):
        for j in range(M):
            if not ones[i][j] or visited[i][j]: continue
            cnt += 1
            # bfs(ones, visited, N, M, (i, j))  # BFS 이용
            dfsByStack(ones, visited, N, M, (i, j))  # 스택으로 구현한 DFS 이용
    
    print(cnt)