음료수 얼려 먹기

💡 문제

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

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

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

⌨️ 입력

• 첫째 줄에 얼음 틀의 세로 길이 N 과 가로 길이 M dl 주어집니다 (1 <= N, M <= 1000)

• 두번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어집니다.

• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.

🖨️ 출력

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

출처: 동빈나 - (이코테 2021 강의 몰아보기) 3. DFS & BFS
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

✅ 풀이!

이 문제의 핵심 키포인트는 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는경우 서로 연결 이라고 생각한다.

즉, 인접한 곳을 살펴보아야 한다는 것인데 내 머리속에선 아! DFS 로 풀어야겠구나 라고 떠올랐다
물론 BFS 로도 해결할 수도 있다는 걸 염두해두고 DFS 함수 내부의 순서를 짜보았다

1. 해당 노드에 인접한 노드 (상, 하, 좌, 우) 를 방문하여 값이 0 이라면 방문을 한다 ( 재귀함수로 구현 )

2. 다시 주변 노드를 방문했는지 확인한다

3. 방문하게 되면 true 라는 값을 반환하고 방문을 하지 않으면 false 를 반환한다

4. 1~2 번의 과정을 반복하여 반환값이 true 일때 카운트를 1 증가 시킨다

🖥️ 소스 코드

func dfs(_ x: Int, _ y: Int) -> Bool {
    if x <= -1 || x >= n || y <= -1 || 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
}

let input = readLine()!.split(separator: " ") .map{ Int($0)! }

let n = input[0]
let m = input[1]

var graph: [[Int]] = []

for _ in 0..<n {
    graph.append(readLine()!.split(separator: " ").map{Int($0)!})
}

var result = 0

for i in 0..<n {
    for j in 0..<m {
        if dfs(i, j) == true {
            result += 1
        }
    }
}

print(result)