Swift) 백준 2468번 안전영역 - S1

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

2468번: 안전 영역

전형적인 경로 탐색 문제. 접근 방식은 for문으로 비의 높이가 지역의 높이보다 낮다면 해당 지역을 시작점으로 계속해서 탐색하고, 만약 더 탐색할 수 없다면 다음 시작점으로 이동해서 이어진 경로를 계속해서 탐색한다. 이때 BFS를 이용해서 문제를 풀었다. visited를 통해 비의 높이에 따라 방문 했는지 체크해서 푸는 방식을 택했다. 다른 사람 풀이를 보니 DFS를 이용해 푼 사람도 있던데 문제의 요점은 비의 높이보다 큰 지역을 모두 방문하는것이니 어느것을 써도 상관 없을 것 같다.

 

import Foundation

let n = Int(readLine()!)!
var map: [[Int]] = []
var maxValue: Int = 0
var answer = 0
let dx = [0,0,1,-1]
let dy = [1,-1,0,0]

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    input.forEach { value in
        maxValue = max(maxValue, value)
    }
    map.append(input)
}
for num in 0..<maxValue {
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)
    var queue: [(Int, Int)] = []
    var areaNum = 0
    for i in 0..<n {
        for j in 0..<n {
            if map[i][j] > num {
                if !visited[i][j]{
                    areaNum += 1
                    queue.append((i, j))
                    while !queue.isEmpty {
                        let popArea = queue.removeFirst()
                        for i in 0..<4 {
                            let nx = popArea.1+dx[i]
                            let ny = popArea.0+dy[i]
                            if nx < 0 || nx >= n || ny < 0 || ny >= n || map[ny][nx] <= num || visited[ny][nx]{
                                continue
                            }
                            queue.append((ny, nx))
                            visited[ny][nx] = true
                        }
                    }
                }
            }
        }
    }
    answer = max(answer, areaNum)
}
print(answer)