간단한 문제 요약
농장에서 산봉우리마다 경비원을 배치하려고 합니다. 그래서 산봉우리의 개수를 구해야 합니다.
산봉우리란 같은 높이를 가지는 인접한 격자(x, y 좌표 차이가 1 이하인 경우)의 집합 이거나 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 합니다.
고려해야 할 사항
- 산봉우리의 높이 차이는 예제 입력 1에서 1씩 차이가 날 수도 있고, 더 클 수 있습니다.
ex) input:
3 1
1
3
1
ans: 1
문제 풀이, 했갈렸던 점
처음에 산봉우리로 부터 인접한 지역 차이가 단순히 1로만 생각했고 0을 기준으로 산봉우리가 나뉜다고 판단을 했습니다. 그런데 위 예제 입력처럼 격자의 차이가 1보다 클 수 있다는 것을 알게 되었습니다.
산봉우리는 인접한 지역보다 가장 높은 지역을 의미합니다. 가장 높은지역이 A가 존재한다면, 바로 인접한 지역 B 들은 가장 높은 산봉우리보다 상대적으로 높이가 낮을 것입니다. B에 인접한 지역들은 B의 높이가 같을수도, 작을 수도 있습니다. 만약 A보다 크다면? 그 지역도 산봉우리가 됩니다.
ex) input:
3 4
3 1 3 1
1 2 1 1
1 1 1 1
ans: 2
그래서 산봉우리의 크기가 결정되는 것은 인접한 지역보다 상대적으로 큰 곳이 있다면 인접한 지역은 산봉우리 측정x!! 인접한 지역보다 내가 가장 크다! 그럼 그 지역이 산봉우리가 되는 것입니다.
코드
import Foundation
typealias Point = (x:Int,y:Int)
let direction = [(-1,0),(-1,1),(0,1),(1,1),
(1,0),(1,-1),(0,-1),(-1,-1)]
var nm = readLine()!.split{$0==" "}.map{Int(String($0))!}
let height = nm[0], width = nm[1]
//산봉우리
var res = 0
var visited = Array(repeating: Array(repeating: false, count: width), count: height)
var farm = (0..<height).map{_ in readLine()!.split{$0==" "}.map{Int(String($0))!} }
func isOutOfBounds(target p: Point) -> Bool{
return p.x<0 || p.y < 0 || p.x > width-1 || p.y > height-1
}
func bfs(p: Point, completion: (Bool) -> Void) {
var queue: [Point] = [p]
var idx = 0
// 초기에 탐색 시작한 지역이 산봉우리에 해당하는 높이인가?(둘러싸인 인접한 지역보다 가장 높다고 판단되는 지역)
var isTop = true
let height = farm[p.y][p.x]
visited[p.y][p.x] = true
defer { completion(isTop) }
while queue.count > idx {
let (cx,cy) = queue[idx]
for (dx,dy) in direction {
let (nx,ny) = (cx+dx,cy+dy)
if isOutOfBounds(target: (nx,ny)) { continue }
// 내가 탐색중인 지역보다 더 높은 지역이 있으므로 현재 탐색중인 지역은 산봉우리 해당x
if farm[ny][nx] > height { isTop = false }
if !visited[ny][nx] && farm[ny][nx] == height {
visited[ny][nx] = true
queue.append((nx,ny))
}
}
idx += 1
}
}
for y in 0..<height {
for x in 0..<width where !visited[y][x] && farm[y][x] != 0 {
bfs(p: (x,y)) { res = $0 ? res + 1 : res }
}
}
print(res)
'백준 PS일지 > DFS&BFS' 카테고리의 다른 글
[백준/Swift] 24445: 알고리즘 수업 - 너비 우선 탐색 2 (0) | 2023.03.24 |
---|---|
[백준/Swift] 6087 : 레이저 통신 (0) | 2023.01.05 |
[백준/Swift] 2933: 미네랄 (0) | 2023.01.02 |
[백준/Swift] 12852 : 1로 만들기 2 (0) | 2022.08.08 |