[알고리즘] 음료수 얼려 먹기

오현우·2022년 5월 7일
0
post-thumbnail

음료수 얼려먹기 문제

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

이때 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 함수를 작성하시오.

아래와 같이 얼음틀이 주어질 경우 아이스크림은 2개 생성된다.
0 0 1
0 1 1
0 1 0

체크해야 할 점

우리가 0인 지점을 방문하였을 때 해당 부분과 접하는 모든 부분들을 처리할 수 있는 방법이 필요하다.

해결방법

이러한 때에는 DFS가 적절한 방법이라고 볼 수 있다.
해당 노드를 방문 하였을때 해당 노드가 0인 경우 인접한 부분들을 먼저 묶어주는 작업을 진행해야 한다. 때문에 LIFO 방법이 적절하며 이러한 방법중 최적인 방법인 DFS를 사용하려고 한다.

DFS

우리는 아래와 같은 과정을 반복하며 모든 노드를 탐색할 예정이다.

  1. 노드를 방문한다.
  2. 방문했던 노드가 아니라면 해당 노드를 방문처리 한 후 카운트를 하나 추가한다.
  3. 해당 노드 상하좌우를 살피며 0인 노드는 방문처리 한다.
  4. 상하좌우 살피며 0인 노드중 다시 상하좌우를 살피며 인접 노드가 없을 때까지 반복한다.
  5. 다음 노드를 방문하며 위의 과정을 반복한다.

여기서 주의할 점은 4번이다. 때문에 4번에 대해서 지속적으로 생각하며 예외사항을 고려하여야 한다.

위의 생각을 파이썬 코드로 구현하면 아래와 같다.

#### 음료수 얼려먹기 문제
import sys

N, M = map(int, input().split())
icebox = []
for _ in range(N):
    icebox.append(list(map(int, sys.stdin.readline().split())))

#### solution
# 해당 노드를 방문처리 한다.
# 해당 위치에서 상하좌우를 살핀다.
# 해당 노드가 0인 경우 stack 에 추가해서 나중에 살펴볼 노드로 추가한다. 
# 더이상 살필 노드가 없으면 계속해서 0이면서 탐색하지 않은 노드를 찾으면 위의 과정을 반복한다.

def dfs(graph, x, y):
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(graph, x-1, y)
        dfs(graph, x+1, y)
        dfs(graph, x, y-1)
        dfs(graph, x, y+1)
        return True
    
    else:
        return False

cnt = 0
for i in range(N): # 행
    for j in range(M): # 열
        if dfs(icebox, i, j):
            cnt += 1
print(cnt)```

profile
핵심은 같게, 생각은 다르게

0개의 댓글