알고리즘 | 음료수 얼리기 문제 (BFS와 DFS로 각각 풀어보기)

N by M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0 칸막이가 존재하는 부분은 1입니다.  구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 판단합니다. 이러한 경우에서 얼음 틀의 모양이 그래프로 주어진다면 생성되는 아이스크림의 갯수는 몇 개일까요?

graph_45 = [
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]

n = 4
m = 5

 

첫째 / BFS 방식으로 풀기

 

출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다.

일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다.

 

from collections import deque

 

 

1. 함수를 작성합니다. 입력받은 출발점 좌표로부터 시작하여 출발점 좌표가 1이면 바로 False를 리턴하고, 출발점 좌표가 0이면 주변을 탐색하면서 0이 있으면 1로 바꾸고, 더이상 바꿀 0이 없는 경우에는 True를 리턴하는 함수를 작성합니다.

2. 함수 작성 이후, 주어진 그래프의 (0, 0)부터 시작하여 n*m 좌표마다 함수를 적용하도록 이터레이션을 돌립니다. True가 반환되는 갯수가 곧 음료수 얼음 덩어리의 갯수가 됩니다.

 

def ice_bfs(row_init, col_init):
    # 만약 주어진 좌표가 0이라면 가보자고!
    if graph[row_init][col_init] == 0:
        q = deque([[row_init, col_init]])
        # ---------------------------------------- 무한 루프 
        while True:
            if not q:
                return 1

            row, col = q.popleft()
            for [dx, dy] in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                # 이동한 값이 지도 안에 있고
                if 0 <= row + dx < n and 0 <= col + dy < m:
                    # 얼릴 수 있다면
                    if graph[row+dx][col+dy] == 0:
                        # 1번 도장을 찍고, 그 다음 할일 추가하세요
                        graph[row+dx][col+dy] = 1
                        q.append([row+dx, col+dy])
        # ---------------------------------------- 무한 루프 
    else:
        return 0

result = 0

for row in range(n):
    for col in range(m):
        result += ice_bfs(row, col)

print(result)
# 3

 

 

둘째 / DFS 방식으로 풀기

위에서 작성한 함수를 DFS방식을 활용한 재귀함수로 바꾸어 작성해 봅시다. (같은 기능!)

 

def dfs_recursive(row, col):
    # 주어진 점이 틀 밖이라면 바로 함수 종료
    if row <= -1 or row >= n or col <= -1 or col >= m:
        return False
    
    # [1] 주어진 점이 0이라면 True를 반환
    if graph[row][col] == 0:
        
        graph[row][col] = 1  # 일단 True 반환 전에 0->1로 바꾸고
        dfs_recursive(row, col-1)
        dfs_recursive(row-1, col)
        dfs_recursive(row, col+1)
        dfs_recursive(row+1, col) # 상하 좌우도 전부 점검해주기!

        return True

    # [2] 주어진 점이 1이라면 False를 반환
    else:
        return False

 

같은 방식으로 모든 좌표점에 작성한 함수를 돌려주면서 True가 반환되는 개수를 세어 주면 끝~

 

result = 0

for row in range(n):
    for col in range(m):
        result += dfs_recursive(row, col)

print(result)
# 3

 

 

 

짱짱 재밌군!

BFS도 DFS도 자유자재로 활용할 수 있도록 열심히 반복!

 

 

다음 문제로는 카카오 2022 블라인드 공개채용 <양과 늑대> 문제를 풀어봅시다...