본문 바로가기

백준 PS일지/DFS&BFS

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

문제

 

1245번: 농장 관리

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수

www.acmicpc.net

간단한 문제 요약

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

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