[이코테] 음료수 얼려 먹기 - python

문제

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

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

다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

▶️ 입력 조건 

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0 그렇지 않은 부분은 1이다.

▶️ 출력 조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

---

풀이

개인적으로 정말 애먹었던 문제이다. 그렇지만 결과적으로는 해당 문제를 해결함으로써 재귀함수를 왜 사용하는지에 대한 이해도가 확실하게 상승하였다. 평소에는 알고리즘에서 재귀함수가 어떤식으로 사용될지 감이 안잡혔으나 이번 문제를 통해 감을 잡았다.

 

애먹었던 이유는 애시당초 문제 자체가 잘 이해가 가지 않았었다.

예시를 보면 구멍이 뚫린 부분이 11개인데 어떻게 3개가 나오는지 이해가 가지 않았다.

"상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다." 라고 친절히 나와있는데 이 문구를 제대로 이해하지 못했다......

 

어쨋든 거두절미하고 해당 예시에서 아이스크림은 아래와 같이 3개 생성된다.

 

 

"상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주" 라는 의미는 위와 같이 붙어있는 경우 하나의 아이스크림이 된다는 뜻이다.

 

그렇다는 것은 0이 발견 될 경우 아이스크림 개수를 +1 해주고,

동시에 주변에 붙어 있는 모든 0 부분을 1로 바꾸어 주면 된다고 생각했다.

그러나 막상 코드를 작성하려 해도 감이 잘 잡히지 않아서 힌트를 보게되었고,

"재귀함수" 라는 힌트를 보고 비로소 이해하게 되었다.

 

0이 발견될 경우 재귀함수를 통해 상하좌우를 모두 방문하도록 로직을 짜는 것이다.

이렇게 한다면 0이 발견된 순간 재귀함수를 통해 그 주변 0들은 모두 1로 변경 될 것이고,

0의 카운트에 따라 아이스크림 개수가 정해지게 되는 것이다.

 

따라서 본인은 아래와 같이 구현하였다.

n,m = map(int, input().split())
map_list = []
for _ in range(n):
    map_list.append(list(map(int, input())))
    
def make_ice_juice(x, y):
    # 범위를 벗어날 경우 False
    if (x < 0) or (n-1 < x) or (y < 0) or (m-1 < y):
        return False
    
    if map_list[x][y] == 0:
        
        # 해당 얼음틀 방문 처리
        map_list[x][y] = 1
        
        # 상하좌우를 재귀적으로 방문
        make_ice_juice(x, y-1) # 상
        make_ice_juice(x, y+1) # 하
        make_ice_juice(x-1, y) # 좌
        make_ice_juice(x+1, y) # 우
        
        # 이렇게 하면 주변에 모든 0에 방문 한것으로 처리 그렇기 때문에 하나의 아이스크림 탄생
        return True
    
    # 1일 경우에는 False 반환
    return False

count = 0

# 2차원 for문을 통해 모든 얼음 틀에 방문
for x in range(n):
    for y in range(m):
        if make_ice_juice(x, y):
            count += 1

print(count)