[Algorithm] 백준 - 2667번 단지번호 붙이기 (Swift)

문제 소개

https://www.acmicpc.net/problem/2667

DFS, BFS 로 모두 풀 수 있는 문제여서 두가지 방법을 사용해 보았다.
 

문제 풀이

DFS 풀이

우선 dfs를 활용한 풀이는 재귀함수를 사용했다.

import Foundation

let n = Int(readLine()!)!
var visit = Array(repeating: Array(repeating: false, count: n), count: n)
var graph = [[Int]]()

for _ in 0..<n {
    let input = Array(readLine()!).map { Int(String($0))! }
    graph.append(input)
}

var total = 0
var counts = [Int]()

for i in 0..<n {
    for j in 0..<n {
        if !visit[i][j] && graph[i][j] == 1 {
            total += 1
            var count = 1
            visit[i][j] = true
            
            func dfs(_ i: Int, _ j: Int) {
                let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
                
                for direction in directions {
                    let i = i + direction.0
                    let j = j + direction.1
                    
                    if i >= 0 && i < n && j >= 0 && j < n {
                        if !visit[i][j] && graph[i][j] == 1 {
                            visit[i][j] = true
                            count += 1
                            dfs(i, j)
                        }
                    }
                }
            }
            
            dfs(i, j)
            counts.append(count)
        }
    }
}

print(total)
for count in counts.sorted() {
    print(count)
}

BFS 풀이

큐를 사용하여 문제를 풀었다.

import Foundation

let n = Int(readLine()!)!
var visit = Array(repeating: Array(repeating: false, count: n), count: n)
var graph = [[Int]]()

for _ in 0..<n {
    let input = Array(readLine()!).map { Int(String($0))! }
    graph.append(input)
}

var total = 0
var counts = [Int]()

for i in 0..<n {
    for j in 0..<n {
        if !visit[i][j] && graph[i][j] == 1 {
            var count = 1
            total += 1
            visit[i][j] = true
            
            let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            var queue = [(i, j)]
            
            while !queue.isEmpty {
                let poped = queue.removeFirst()
                
                for direction in directions {
                    let i = poped.0 + direction.0
                    let j = poped.1 + direction.1
                    
                    if i >= 0 && i < n && j >= 0 && j < n {
                        if !visit[i][j] && graph[i][j] == 1 {
                            visit[i][j] = true
                            count += 1
                            queue.append((i, j))
                        }
                    }
                }
            }
            
            counts.append(count)
        }
    }
}

print(total)
for count in counts.sorted() {
    print(count)
}

 

결과

N이 25이하이기 때문에 두 풀이에 큰 차이는 없어보인다.