[이코테] chap5-3. 음료수 얼려먹기

이 문제는 DFS로 풀라고 나와있지만 BFS가 익숙한 나머지 BFS로 하다 한참이 걸렸다..


'0'인 노드들로 묶인 묶음을 카운트 하는 문제로 이러한 묶음을 찾아주는 프로그램은 DFS로 풀면 간단하다.
(특정 시작 노드로 부터 깊이 들어가기 때문, BFS는 연결된 노드마다 주변을 살피느라 더 오래걸린다)

BFS 코드

from collections import deque

def bfs(matrix, start):
    # 상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque([start])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            elif matrix[nx][ny] == 1:
                continue

            elif matrix[nx][ny] == 0:
                queue.append((nx, ny))
                matrix[nx][ny] = 1

    return matrix

####main
n, m = map(int, input().split())
matrix = []

for _ in range(n):
    temp = []
    s = input()
    for i in range(m):
        temp.append(int(s[i]))
    matrix.append(temp)

result = 0

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 0:
            matrix[i][j] = 1
            matrix = bfs(matrix, (i, j))
            result += 1

print(result)

DFS 코드

#input 값 넣기
n, m = map(int, input().split())
matrix = []
result = 0

for _ in range(n):
    matrix.append(list(map(int, input())))

## DFS 로 구현한 코드
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if matrix[x][y] == 0:
        # 해당 노드 방문 처리
        matrix[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

## main
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1

print(result)

후기

BFS는 queue에 주변 칸을 추가한 후 큐에서 다시 꺼내면서 방문 했던 주변도 다시 탐색하므로 반복해서 방문하는 노드가 너무 많아진다.

따라서 이런 문제는 재귀형식을 사용하는 DFS를 이용하여,
이미 1로 바뀐 matrix 칸을 반영하여 다음 dfs함수에선 시작 노드가 1인 경우 빠르게 컷하는 형태가 된다.

핵심은 묶음 처리로 푸는 문제는 DFS, 0인 얼음을 방문한 경우 다시 벽처럼 1로 만드는 것이다.
굳이 다른 숫자나 visited 변수를 만들려다 오래 걸렸다.