[Swift] 백준_안전 영역(2468)

문제

 

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

2468번: 안전 영역

 

 

풀이

 

region 변수에 높이 정보를 담으면서 동시에 height라는 배열에도 입력값을 넣어주었다. 이후에 height에 Set을 씌워 중복을 제거하면 입력에 들어온 모든 높이를 배열에 담을 수 있다.

 

물이 잠기는 높이마다 영역이 얼마나 생길지는 다 확인해봐야 알 것 같았다.

그래서 위에서 구한 height의 원소별로 각각 영역을 구해주었다.

 

이후의 풀이는 다른 기본적인 bfs문제들과 동일하다.

일단 이 문제는 최소시간같은 문제가 아니므로 방문하지 않은 영역이 없도록 전부 확인해야한다. 그래서 for문의 중첩을 통해 일단 모든 점을 방문할 수 있도록 해주었고, 이때 방문하지 않았으며 region이 cur보다 크거나 같으면 큐에 추가해주었다.

 

위에서 한 것은 영역의 시작점을 찾은 것이다. 이 점을 기준으로 while문을 상하좌우로 움직이면서 잠기지 않는 영역을 찾게되면 다시 큐에 넣어 이어지는 영역들을 전부 확인해주도록 하였다.

 

이렇게 한 영역을 전부 탐색하고나면 밖의 for문으로 다른 시작점(방문하지 않았으며 잠기지 않은 영역)을 찾아서 반복해준다.

 

구한 값들의 최대값을 출력해주면 된다.

import Foundation

let n = Int(readLine()!)!
var region: [[Int]] = []
var result = 1
var height: [Int] = []
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    region.append(input)
    height += input
}
height = Array(Set(height))

for cur in height {
    var queue: [[Int]] = []
    var visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var count = 0
    for i in 0..<n {
        for j in 0..<n {
            if !visited[i][j] && region[i][j] >= cur {
                queue.append([i,j])
                visited[i][j] = true
                count += 1
                while !queue.isEmpty {
                    let current = queue.removeFirst()
                    for k in 0..<dx.count {
                        let newX = current[0] + dx[k]
                        let newY = current[1] + dy[k]
                        if newX < 0 || newY < 0 || newX >= n || newY >= n {
                            continue
                        }
                        if visited[newX][newY] || region[newX][newY] < cur {
                            continue
                        }
                        queue.append([newX,newY])
                        visited[newX][newY] = true
                    }
                }
            }
        }
    }
    result = max(result,count)
}
print(result)

 

 

_____________________________________________________________________________________________________

 

생각했으면 바로 구현해보기