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

https://www.youtube.com/watch?v=7C9RgOcvkvo

이 문제의 해설 영상이다.

문제

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

 

입력 조건:

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

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

 

정답 코드

n, m = map(int, input().split())
graph = [list(map(int, input())) for i in range(n)]

def dfs(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(x - 1, y)
        dfs(x, y + 1)
        dfs(x + 1, y)
        dfs(x, y - 1)
        return True
    return False

result = 0
for i in range(n):
     for j in range(m):
         if dfs(i, j) == True:
             result += 1

print(result)

처음 풀어본 탐색 문제였기 때문에 한 번에 풀지 못했다. 탐색 문제에서는 리스트의 원소들을 그래프의 노드들로 생각하여 풀어야 한다. 이 문제는 모든 노드를 탐색하는 문제이기 때문에 DFS나 BFS 둘 다 사용 가능하다. 책의 솔루션에서는 DFS를 사용하여 간결하게 구현하였다. 

 

dfs 함수를 보면 어떤 노드를 방문한 뒤, 해당 노드를 방문 처리하고 상, 하, 좌, 우의 노드에서 모두 재귀적으로 dfs함수를 호출하는 방식으로 dfs 탐색을 구현하였다. 이렇게 하면 이중 for문에서 dfs를 사용하여 모든 노드를 방문할 때 그 노드를 이미 재귀적으로 방문했다면 graph[x][y]가 1이기 때문에 result에 포함되지 않으므로 노드를 처음 방문할 때만 result++ 하는 방식으로 정답을 구할 수 있다.  

 

배울 점

처음 풀어본 탐색 문제라 감이 안와 빠르게 솔루션을 본 감이 없지 않다. 지금 보면 이전에 이용했던 dx, dy를 통해서도 풀 수 있을 것 같은데 시도조차 안 해본 것이 아쉽다. dfs와 bfs를 각각 어떤 문제에 적용하는지 공부를 해서 다양한 탐색 문제를 풀어봐야겠다.

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)