[백준/Swift] 1245: 농장 관리 | PS일지

문제

1245번: 농장 관리

간단한 문제 요약

농장에서 산봉우리마다 경비원을 배치하려고 합니다. 그래서 산봉우리의 개수를 구해야 합니다.

산봉우리란 같은 높이를 가지는 인접한 격자(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)