[Swift 알고리즘] 백준 BOJ - 2667 단지번호붙이기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 2667 단지번호붙이기" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

2667번: 단지번호붙이기

 

---

풀이

이번 문제는 그래프 탐색 문제입니다.

저는 dfs를 이용해 문제를 해결했습니다.

 

2차원 배열의 모든 원소에 대해 방문하지 않은 원소가 있다면 dfs 탐색을 시도합니다.

map[i][j]의 원소에 접근하면 visited[i][j]를 true로 바꿔주고 map[i][j]의 상하좌우를 체크합니다.

상하좌우 중 방문하지 않았고 값이 1인 곳이 있으면 dfs 탐색을 시도합니다.

 

위 로직을 반복하며 dfs로 더이상 탐색을 못할 때까지 depth를 들어가고 탐색이 끝나면 탐색 횟수를 배열에 저장합니다.

마지막에 배열의 길이가 탐색한 구역의 개수와 동일하고, 각 구역의 탐색 횟수를 출력하면 됩니다.

 

개인적으로 dfs는 재귀가 직관적이고 코드 작성도 쉽다고 느껴집니다.

아직 swift로 bfs는 익숙하지 않네요. 많이 연습해야 겠습니다.

 

번외

오늘 푼 코드가 2년 전 C++로 푼 코드와 거의 비슷하더라고요.

2년 전의 저와 지금의 저는 생각하는 게 똑같았나 봅니다.

기분이 묘했네요 ㅋㅋ

 

---

전체 코드

//2667 단지번호붙이기
import Foundation

let count = Int(readLine()!)!
var map: [[Int]] = Array(repeating: [], count: count)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: count), count: count)

var result: Int = 0
var results: [Int] = []

for i in 0..<count {
    let input = readLine()!.map { Int(String($0))! }
    map[i].append(contentsOf: input)
}

let di: [Int] = [1, -1, 0, 0]
let dj: [Int] = [0, 0, -1, 1]
func dfs(_ i: Int, _ j: Int) {
    if visited[i][j] {
        return
    } else {
        visited[i][j] = true
        result += 1
        
        for k in 0..<4 {
            let i2 = i + di[k]
            let j2 = j + dj[k]
            if i2 >= 0 && i2 < count && j2 >= 0 && j2 < count {
                if map[i2][j2] == 1 {
                    dfs(i2, j2)
                }
            }
        }
    }
}

for i in 0..<count {
    for j in 0..<count {
        if !visited[i][j] && map[i][j] == 1 {
            result = 0
            dfs(i, j)
            results.append(result)
        }
    }
}

results.sort()
print(results.count)
for result in results {
    print(result)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.