음료수 얼려 먹기

델리만쥬 디퓨저·2024년 8월 11일

알고리즘

목록 보기

5/15

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

입력 조건

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)

두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.

이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력 조건

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

문제 접근 아이디어

이 문제는 보자마자 느낌이 딱 왔다. 우선 입력받은 얼음 틀을 2차원 배열로 선언하고, 첫 칸부터 BFS나 DFS 알고리즘을 사용해서 값이 0인 칸만 탐색을 한다. 그러다가 종료되면 탐색되지 않은 다음 칸부터 다시 BFS나 DFS 알고리즘을 돌린다. 얼음 틀이 모두 탐색되면 최종 갯수 출력하면 끝.

여기서 문제. BFS와 DFS 둘 중 어떤 알고리즘을 사용해야 할까? 아마 BFS가 맞지 않을까? 잘 모르겠지만 그럼 일단~은 BFS로 코드를 구현해보자.

BFS로 구현한 코드

from collections import deque

N, M = map(int, input().split())

# 2차원 배열 입력
arr = [[] for _ in range(N)]
for i in range(N):
    arr[i] = list(map(int, input()))

# visited 배열 생성
visited = [[] for _ in range(N)]
for i in range(N):
    visited[i] = [False] * M

count = 0

# BFS
def bfs(arr, x, y, visited):
    queue = deque([(x, y)])
    visited[x][y] = True
    print("새 아이스크림 발견!")
    global count
    count += 1
    while queue:
        v = queue.popleft()
        print(v)
        x, y = v
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and arr[nx][ny] == 0:
                queue.append((nx, ny))
                visited[nx][ny] = True

for i in range(N):
    for j in range(M):
        if visited[i][j] == False and arr[i][j] == 0:
            bfs(arr, i, j, visited);

print('한 번에 만들 수 있는 아이스크림의 개수는 ', count, '개입니다.')

결과

어려웠던 점

상하좌우 및 좌표의 조건을 신경쓰는 것이 조금 까다로웠다.
탐색이 끝난 후 새로운 아이스크림을 찾는 코드를 구현하는 방법을 떠올리는데 시간이 좀 걸렸다.

자 이제 DFS로도 구현해 보자. 이전 코드에서 약간만 수정하면 된다.

DFS로 구현한 코드

from collections import deque

N, M = map(int, input().split())

# 2차원 배열 입력
arr = [[] for _ in range(N)]
for i in range(N):
    arr[i] = list(map(int, input()))

# visited 배열 생성
visited = [[] for _ in range(N)]
for i in range(N):
    visited[i] = [False] * M

count = 0

# DFS
def dfs(arr, x, y, visited):
    visited[x][y] = True
    if arr[x][y] == 1:
        return
    print(x, y)
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            dfs(arr, nx, ny, visited)

for i in range(N):
    for j in range(M):
        if visited[i][j] == False and arr[i][j] == 0:
            count += 1
            print("새 아이스크림 탐색 시작!")
            dfs(arr, i, j, visited);

print('한 번에 만들 수 있는 아이스크림의 개수는 ', count, '개입니다.')