[이것이 코딩 테스트다] 음료수 얼려먹기

문제상황

N by M 크기의 얼음 틀이 있다.

구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1이라 한다.

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

이러한 경우에서 얼음 틀의 모양이 주어진다면 생성되는 아이스크림의 개수는?

 

입력조건 

- 첫 번째 줄에 얼음 틀의 세로 길의 N과 가로 길이 M이 주어진다. (1 ≤ N, M ≤ 1000)
- 두 번째 줄부터 N+1 까지 얼음 틀의 형태가 주어진다.
- 구멍이 뚫린 부분은 0, 아닌 부분은 1로 나타낸다.

 

출력 조건 

- 한 번에 만들 수 있는 아이스크림의 개수 출력

 

입출력 예시

입력 예시 : 4 5
                   00110
                   00011
                   11111
                   00000
출력 예시 : 3

 

아이디어

1. BFS, DFS 등 적절한 탐색 알고리즘 결정
2. 그래프를 좌표로 표현하고 이동할 수 있는 방향으로 진행
3. 탐색한 곳이 1인 경우와 0인 부분을 구분하여 다음 단계 진행

구현

CASE 1

graph =[
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]
n = 4
m = 5

from collections import deque
def ice_bfs(row_init, col_init):
    if graph[row_init][col_init] == 0:
        graph[row_init][col_init] = 1
        q = deque([[row_init, col_init]])
        while True:
            if not q:
                return 1
            row, col = q.popleft()
            for dx, dy in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                if 0 <= row + dx < n and 0 <= col + dy < m:
                    if graph[row + dx][col + dy] == 0:
                        graph[row + dx][col + dy] = 1
                        q.append([row + dx, col + dy])
    else:
        return 0
        
result = 0
for row in range(n):
    for col in range(m):
        result += ice_bfs(row, col)
print(result)

 

CASE 2

graph =[
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]
n = 4
m = 5

def dfs_recursive(row, col):
    if row < 0 or row >= n or col < 0 or col >= m:
        return False
    if graph[row][col] == 0:
        graph[row][col] = 1
        dfs_recursive(row, col-1)
        dfs_recursive(row, col+1)
        dfs_recursive(row-1, col)
        dfs_recursive(row+1, col)
        return True
    return False

result = 0
for row in range(n):
    for col in range(m):
        if dfs_recursive(row,col) == True:
            result += 1
print(result)

 

탐색 문제는 상황에 맞는 적절한 알고리즘을 선택하는 것이 우선 과제이다.

최단 거리를 구해야 하는 문제는 BFS, 경로의 특징을 저장하면서 해야하는 문제는 DFS를 이용하는 것이 적절하다.

그래프의 모든 점을 방문해야 하는 문제는 BFS, DFS 모두 이용 가능하지만 속도적인 면에서 BFS가 효율적일 수 있다. 

---

문제 출처 : 이것이 코딩 테스트다.