문제
구멍 : 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 |