[Swift 알고리즘] 백준 2468 안전 영역

안녕하세요 코코종입니다..

1일 1알고를 하다가 어제는 일정이 너무... 바빠서 풀수가 없었네요 ㅜㅜ

오늘도 가볍게 풀고 지나가려다가 후.... 이상한 곳에서 꼬여서 시간을 또옹오오오오ㅗ 허비했네요.

참고로 이제 챗 gpt 진짜 절대 안물어볼거임... 멍충이임..

import Foundation

let n = Int(readLine()!)!
var arr: [[Int]] = []
var maxHeight = 0 // 지대의 최대 높이
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    arr.append(input)
    maxHeight = max(maxHeight, input.max()!)
}

var answer = 0
let defaultVisited = Array(repeating: Array(repeating: false, count: n), count: n)
var visited = defaultVisited

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

    return cnt
}

func bfs(i: Int, j: Int, h: Int) {
    let dr = [-1, 0, 1, 0]
    let dc = [0, 1, 0, -1]

    var queue: [[Int]] = []
    queue.append([i, j])

    while !queue.isEmpty {
        let q = queue.first!
        let r = q[0]
        let c = q[1]
        queue.removeFirst()

        if arr[r][c] > h { // !visited[r][c] 조건이 들어가있었다.. 생각해보니 이미 bfs로 들어갈 때 방문 처리를 해버려서 else 처리가 되었다.
            visited[r][c] = true

            for d in 0..<4 {
                let rr = r + dr[d]
                let cc = c + dc[d]

                if rr >= 0, rr < n, cc >= 0, cc < n, !visited[rr][cc], arr[rr][cc] > h {
                    visited[rr][cc] = true
                    queue.append([rr, cc])
                }
            }
        }
    }
}

// 당연히 비가 오는거라서 1부터라고 생각했는데 73퍼에서 틀리길래 설마 했는데 0도 체크를 해줘야 했다... 뭐 이딴...
for h in 0..<maxHeight {
    visited = defaultVisited
    answer = max(answer, bfsAll(h: h))
}

print(answer)

사실 문제 자체는 어렵지 않습니다.

수위를 올려가며(?) 그때마다 bfs를 해주고 answer를 더 큰 값으로 갱신해주면 되는 것이었답니다.

 

제가 틀린 부분은 저기 주석으로 달아뒀는데... 처음에 bfs 처리를 할때 사용한 조건을 그대로 놔두고 하다보니 조건이 꼬였답니다... queue를 Print 찍어봤을때 알았어야하는데.. 이렇게 하나 배워가는 거겠죠...?(꼭 복습해서 다음에는 안이런다는 마인드)

그리고 마지막에는 73%에서 틀리길래 설마! 했더니 역시나 비가 안오는...(하...) 경우도 있었답니다 ^^...