이코테 2021, BFS/음료수 얼려먹기 (파이썬) (전형적인 DFS문제 BFS로 풀어보기)

문제 정의

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

 

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

입력

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

 

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

 

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

 

 

출력

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

 

 

예제 입력 1

4 5
00110
00011
11111
00000

 

예제 출력 1

3

 

 

 

접근 방법

1. 맵의 위치를 하나씩 받아 BFS를 돌린다. 

2-1. BFS에서는 그 곳이 빈 얼음틀일 경우 현재 위치를 방문 처리 및 큐에 삽입/삭제한 뒤, 상하좌우의 위치를 확인하고 해당 위치가 빈 얼음틀일 경우 큐에 해당 위치를 삽입한다.

2-2. BFS에서는 그 곳이 빈 얼음틀이 아닐 경우 0을 반환한다.

3. 큐가 비었을 때 1을 반환하고 BFS를 종료한다. 

4. 1 ~ 3번을 n x m 번만큼 반복하고 BFS가 하나씩 돌아갈 때마다 값을 하나씩 증가시켜준다.

 

코드

from collections import deque

n, m = 4, 5
condition = [list(map(int, input().split())) for _ in range(n)]


def bfs(row, col):
    """col, row : 시작 지점에 대한 행 열"""

    # 입력된 값이 0일 때, 즉 얼음을 만들 수 있는 공간일 때
    if condition[row][col] == 0:
        # 큐 생성
        queue = deque([[row, col]])
        # 방문 지점 표시
        condition[row][col] = 1
        # queue가 없어질 때까지 반복 후 없어지면 값을 1 추가하고 break
        while True:
            if not queue:
                return 1
            row, col = queue.popleft()
            # 상하좌우로 이동하며 이동한 장소가 0일 떄 큐에 추가
            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                # 이동한 장소가 주어진 범위 이내인 지 확인
                if 0 <= row+dy <= n-1 and 0 <= col+dx <= m-1:  
                    if condition[row+dy][col+dx] == 0:
                        queue.append([row+dy, col+dx])
                        # 방문 지점 표시
                        condition[row+dy][col+dx] = 1
    return 0
    
result = 0
for row in range(len(condition)):
    for col in range(len(condition[row])):
        result += bfs(row, col)

print(result)

- 전형적인 DFS 문제이지만 BFS로도 문제를 풀어봤다.