[이것이 코딩 테스트다 with Python] [Python] 음료수 얼려 먹기 (책 해설과 다른 풀이)

목차

 

1. 문제 내용

2. 문제 해석

3. 최종 코드

4. 마무리

---

1. 문제 내용

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

 

# 입력 조건

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

# 출력 조건

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

---

2. 문제 해석

일반적인 그래프 탐색 문제이다. 책에서는 그래프를 탐색하며 구멍(숫자 0)을 발견하면 재귀 함수로 그래프에서 인근 구멍을 탐색하며 구멍들을 채우고(1) 다시 새로운 구멍을 찾아가며 개수를 카운트하는 방법을 사용하였다.

물론 책에 나온 방법도 재귀함수를 이용한 BFS이지만 나는 큐 자료구조를 이용하여 BFS를 구현해보려고 한다. 여기서 일반 BFS와 다른 점은 굳이 방문 확인을 하지 않아도 된다는 것이다. 미리 눈치를 챈 사람도 있겠지만 우리는 그래프상에서 방문한 곳의 0을 1로 바꿀 예정이기에 숫자 0과 1을 방문 배열의 True, False 역할로 이용할 것이기 때문이다.

그 외의 구현은 일반적인 BFS 구현과 동일하다 아래 코드를 보며 이해해보자.

---

3. 최종 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
direc = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4방향에 해당하는 좌표를 미리 할당함
graph = [list(map(int, list(input().strip()))) for _ in range(N)]

def BFS_algo(row, col):
    queue = deque()
    queue.append([row, col])
    graph[row][col] = 1

    while queue:
        now_r, now_c = queue.popleft()
        for r, c in direc:
            new_r = now_r + r
            new_c = now_c + c
            if 0 <= new_r < N and 0 <= new_c < M:
                if graph[new_r][new_c] == 0: # 이 줄 덕분에 우리는 방문처리 배열을 만들지 않아도 된다
                    queue.append([new_r, new_c])
                    graph[new_r][new_c] = 1 # 미리 변경하는 이유는 큐에 중복되는 좌표를 넣지 않기 위해서
    return True

count = 0

for i in range(N):
    for j in range(M):
        if graph[i][j] == 0: # 새로운 구멍이 발견되면
            BFS_algo(i, j) # 그 주변 구멍들을 다 매꾸고
            count += 1

print(count)

---

4. 마무리

마지막으로 재귀함수와 반복문은 어느 부분에서 차이가 있고 어떤 장단점이 있는지 이야기 하며 마치겠다.

재귀함수는 함수가 함수를 낳고 그 함수가 또 다른 함수를 낳으며 종료 조건까지 계속 반복하는 구조다. 함수를 실행하면 매개변수, 지역변수, 리턴 값,,, 등등을 컴퓨터 프로세스 Stack에 저장해야하므로 재귀함수를 이용한 방법은 메모리를 많이 사용하게 되고(stack overflow의 위험 또한 증가시킨다) context switching과 같은 추가적인 cost도 발생시키기에 일반적인 반복문에 비하여 속도가 많이 느리다. (tail recursion이라는 방법을 사용하면 위 문제점들을 줄이거나 없앨 수 있다)

큐를 이용한 반복문은 동일한 변수를 지속해서 사용하고 재귀 함수와 다르게 context switching 또한 발생시키지 않기에 재귀함수를 이용한 문장보다 실행속도가 빠르다.

그렇다면 항상 반복분을 사용한 풀이가 이상적일까??

물론 실행 속도 측면에서는 재귀함수가 반복문을 따라가기 힘들다. 그러나 재귀함수는 변수 사용을 줄여줄 수 있고 문제를 직관적인 풀이 or 점화식을 기반으로 해결할 수 있도록 하기에 디버깅이나 수학적으로 증명이 쉬워지는 장점들이 있어 코드를 작성하는 사람의 입장에서 재귀함수는 훨씬 간편하고 사이드 이펙트(side effect)를 줄여줄 수 있는 좋은 구현 방법 중 하나가 될 수 있다.

우리가 어떤 측면을 중요하게 생각하는지에 따라 풀이 방법은 유연하게 바뀔 수 있는 것이다.