본문 바로가기

Algorithm/DFS and BFS

음료수 얼려먹기

 

문제

구멍 : 0, 칸막이 : 1

구멍이 뚫려있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결되어 아이스크림 생성

아이스크림의 수는?

 

 

유형 파악

우선 아이스크림을 만들려면 연결된 노드들을 파악하다가 더이상 연결된 노드들을 찾을 수 없을 때 아이스크림 하나가 생긴다.

따라서, 연결된 모든 노드들을 탐색할 수 있는 DFS/BFS를 사용할 수 있는데, 둘 다 사용이 가능하다.

 

 

코드

def dfs(array, visited, start):
    x = start[0]
    y = start[1]
    visited[x][y] = True

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    for i in range(4):
        next_x = x+dx[i]
        next_y = y+dy[i]
        if 0 <= next_x < len(array) and 0 <= next_y < len(array[0]):
            if visited[next_x][next_y] == False and array[next_x][next_y] == 0:
                dfs(array, visited, [next_x, next_y])
    return 1


from collections import deque
def bfs(array, visited, start):

    queue = deque()
    queue.append(start)
    visited[start[0]][start[1]] = True

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if 0 <= next_x < len(array) and 0 <= next_y < len(array[0]):
                if visited[next_x][next_y] == False and array[next_x][next_y] == 0:
                    visited[next_x][next_y] = True
                    queue.append([next_x, next_y])
    return 1



array = [
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]
visited = [[False]*len(array[0]) for _ in range(len(array))]
result = 0
for i in range(len(array)):
    for j in range(len(array[0])):
        if visited[i][j] == False and array[i][j] == 0:
            result += dfs(array, visited, [i, j])
print(result)

'Algorithm > DFS and BFS' 카테고리의 다른 글

경쟁적 전염  (0) 2023.04.10
연구소  (0) 2023.04.10
특정 거리의 도시 찾기  (0) 2023.04.10
미로탈출  (0) 2023.04.10
DFS BFS - Concept  (0) 2023.04.10