[백준] 안전 영역 (2468)

문제 설명

백준 2468번 문제 링크

입력 및 출력

» 입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

» 출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입출력(테스트케이스)

입력	출력
5 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7	5
7 9 9 9 9 9 9 9 9 2 1 2 1 2 9 9 1 8 7 8 1 9 9 2 7 9 7 2 9 9 1 8 7 8 1 9 9 2 1 2 1 2 9 9 9 9 9 9 9 9	6

문제 힌트

아무 지역도 물에 잠기지 않을 수도 있다.

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ2468_SWIFT
//
//  Created by choiyoujun on 2022/03/11.
//

func bfs(h: Int, x: Int, y: Int, check: inout [[Bool]]) {
    var q = [(x, y)]
    var left = 0
    let dx = [0, 1, 0, -1]
    let dy = [1, 0, -1, 0]
    
    while left < q.count {
        let current = q[left]
        
        for i in 0..<4 {
            let nx = current.0 + dx[i]
            let ny = current.1 + dy[i]
            
            if nx >= 0 && nx < N && ny >= 0 && ny < N {
                if map[ny][nx] > h && !check[ny][nx] {
                    q.append((nx, ny))
                    check[ny][nx] = true
                }
            }
        }
        
        left += 1
    }
}

let N = Int(readLine()!)!
var map = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)
var set = Set<Int>()
var ans = 1

for i in 0..<N {
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    map[i] = line
    
    for int in line {
        set.insert(int)
    }
}

for h in [Int](set).sorted(by: <) {
    var check = [[Bool]](repeating: [Bool](repeating: false, count: N), count: N)
    var count = 0
    
    for y in 0..<N {
        for x in 0..<N {
            if map[y][x] > h && !check[y][x] {
                check[y][x] = true
                count += 1
                bfs(h: h, x: x, y: y, check: &check)
            }
        }
    }
    
    ans = max(ans, count)
}

print(ans)