[백준/BOJ] 2468번 안전 영역(Swift)

문제 난이도: 실버 1

 

사용 알고리즘: DFS

import Foundation

let n = Int(readLine()!)!
var map: [[Int]] = []
var heights = Set<Int>()
var sortedHeights = [Int]()
let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var mapCount = 0
var result = 0

for _ in 0 ..< n {
    
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    
    line.forEach { heights.insert($0) }
    
    map.append(line)
}

sortedHeights = heights.sorted()

func dfs(x: Int, y: Int, height: Int) {
    
    if x < 0 || x >= n || y < 0 || y >= n || map[y][x] <= height || visited[y][x] {
        return
    }
    
    visited[y][x] = true
    
    for direction in directions {
        
        let newX = x + direction.0
        let newY = y + direction.1
        dfs(x: newX, y: newY, height: height)
    }
}

for i in sortedHeights {
    for y in 0 ..< map.count {
        for x in 0 ..< map.count {
            if !visited[y][x] && map[y][x] > i {
                dfs(x: x, y: y, height: i)
                mapCount += 1
            }
        }
    }
    
    result = max(result, mapCount)
    mapCount = 0
    visited = Array(repeating: Array(repeating: false, count: n), count: n)
}

print(result == 0 ? 1 : result)

 

일반적인 DFS로 동일하나, height보다 맵의 높이가 낮지 않을때만 탐색하도록 했다.

 

고도에 따라 모두 구해야줘야하기 때문에 1 ... 100을 모두 체크하는 방법도 있겠지만

for문 자체가 3개나 돼서 조금 더 계산을 덜하게 하고 싶었다.

 

이에 map에 저장할 때 같이 Set을 통해 map에 포함된 높이를 모두 저장했다.

Set이기 때문에 중복된 값은 무시된다.

이 후 오름차순으로 map에 포함된 높이들만 체크하였는데, 시간복잡도에는 크게 영향을 끼치진 못한다고 한다.

 

그냥 1 ... 100으로 했어도 풀이에는 문제가 없다.