[백준] Swift 2468 안전 영역 BFS

문제 :

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

2468번: 안전 영역

 

분석 :

문제의 안전 영역의 정의를 처음엔 이해하기 어려웠다. 그래서 얼만큼의 장마가 내린다구 ? 했는데 모든 장마 경우의 수를 다 검사해 안전 영역이 최대가 될때 안전 영역의 개수를 출력하라는 뜻이었다.

bfs를 돌아 visit배열에 false인 영역을 true로 만들고 끝내고 오면 bfsAll 함수에서 하나씩 cnt + 1 하여 안전 영역의 개수를 구해준다.

그 전에 visit 배열을 안전 영역 높이 0부터 시작해 어느 높이까지 검사할텐가가 문제인데 input시 arr배열 안에 최대값을 maxNumber에 기록해 둔뒤 매번 bfsAll 배열을 돌기전 visit 배열을 초기화 시켜 주었고 마지막에 totalArea에 최대값을 구하도록 했다.

 

swift 풀이 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/11.
//

import Foundation
var n = Int(readLine()!)!
var arr: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
var visit = Array(repeating: Array(repeating: false, count: n), count: n)
var dx = [-1, 1, 0, 0]
var dy = [0, 0, 1, -1]

func bfs(_ i: Int, _ j: Int){
   visit[i][j] = true
    var qu = [(Int, Int)]()
    qu.append((i, j))
    
    while(!qu.isEmpty){
        let nx = qu.last!.0
        let ny = qu.last!.1
        qu.removeLast()
        for i in 0..<4 {
            let nextX = nx + dx[i]
            let nextY = ny + dy[i]
            if(nextX >= n || nextX < 0 || nextY >= n || nextY < 0) { continue }
            if(visit[nextX][nextY]) { continue }
            //print("\(nextX) \(nextY)")
            visit[nextX][nextY] = true
            qu.append((nextX, nextY))
        }
        
    }
}

func bfsAll() -> Int {
    var cnt = 0;
    for i in 0..<n {
        for j in 0..<n {
            if(!visit[i][j]){
                bfs(i, j)
                cnt += 1
            }
        }
    }
    return cnt
}

var totalArea = 0
var maxNumber = 0
for i in 0..<n {
    let line = readLine()!.split(separator:  " ").map { Int($0)! }
    for j in 0..<line.count {
        arr[i][j] = line[j]
        if(arr[i][j] > maxNumber){
            maxNumber = arr[i][j]
        }
    }
}

for k in 0..<maxNumber {
    for i in 0..<n {
        for j in 0..<n {
            if(arr[i][j] <= k){
                visit[i][j] = true
            }
        }
    }
    totalArea = max(bfsAll(), totalArea)
    visit = Array(repeating: Array(repeating: false, count: n), count: n) // 다시 초기화
}
print(totalArea)​