[DFS/BFS] 음료수 얼려 먹기

DFS, BFS에 대한 간략한 소개

깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)은 두 가지 널리 쓰이는 그래프 탐색 알고리즘이다.
그래프 탐색의 목적은 그래프 내에서 목표 노드를 찾는 것이다. 이 두가지 모두 사용이 가능한 경우라도 각각의 장단점에 따라 선택하여 문제를 푸는 것이 중요하다.

DFS

DFS는 그래프를 깊게 탐색하는 알고리즘이다.
즉, 한놈만 팬다는 느낌으로 깊게 들어가서 탐색하는 것!

탐색시 시작 노드로부터 방문하지 않은 노드로 가기 위해 스택을 사용한다.
만약 가장 마지막 깊이까지 방문했다면 스택의 가장 위에 있는 노드로 돌아가 스택의 다른 노드들을 방문한다.
DFS는 깊이 들어가기 때문에 목표 노드를 빠르게 찾을 수 있지만 메모리 사용량이 많이 든다는 단점이 있다.

BFS

BFS는 그래프를 넓게 탐색하는 알고리즘이다.
DFS와는 다르게 그래프를 탐색할 때 큐를 사용한다.
그래프에서 꺼낸 방문하지 않은 노드는 큐에 넣고 방문한 노드는 큐에서 제거된다.
BFS는 메모리 사용량이 DFS보다 적지만 목표 노드를 찾는데 시간이 더 오래 걸린다는 단점이 있다.

결론

DFS는 목표 노드를 빠르게 찾을 수 있지만 메모리 사용량이 많이 든다.
BFS는 메모리 사용량이 DFS보다 적지만 목표 노드를 찾는데 시간이 더 오래 걸린다.

[문제] 음료수 얼려 먹기

N × M 크기의 얼음 틀이 있다.
0은 얼음칸, 1은 칸막이로 표시한다.
얼음칸끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
주어진 얼음 틀에서 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성하기.

입력 조건

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

출력 조건

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

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시2

8

풀이

1. 2차원 배열을 만들어 그래프를 입력 받는다.
2. 그래프의 모든 노드를 방문하여 dfs로 탐색한다.
3. dfs 함수 내에서 범위 안에 있고 방문되지 않은 노드를 모두 탐색한다. => if graph[x][y] == 0
   이 때 방문처리를 진행한다. => graph[x][y] = 1
4. 범위밖으로 벗어나거나 주변에 0이 없다면 return false로 재귀 함수들을 종료한다.
5. 즉 dfs함수가 true로 반환될 때 뭉쳐있는 한 덩어리를 모두 방문했으므로 result += 1로 count한다.

코드

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (input[0], input[1])

var graph = [[Int]]()
for _ in 0 ..< n {
    graph.append(readLine()!.map { Int(String($0))! })
}

func dfs(_ x: Int, _ y: Int) -> Bool {
    // 범위 벗어나면 종료
    if !isInRange(x, y) {
        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 // 주변이 다 막혀있다면 true 반환하고 종료
    }
    return false
}

func isInRange(_ x: Int, _ y: Int) -> Bool {
    return (0..<n ~= x) && (0..<m ~= y)
}

var result = 0

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

print(result)