백준 1981 배열에서 이동

출처: www.acmicpc.net/problem/1981

분류: 이분탐색

---

접근방식

이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다.

어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다.

우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다.

그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요.

저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우를 찾았다면, 그보다 큰 경우는 생각할 필요가 없습니다. 따라서 이분탐색으로 범위를 줄여나갈 수 있습니다.

var low = 0
var high = maxValue-minValue

while(low <= high) {
  let mid = (low + high)/2
  if search(mid) {
    minDiff = min(minDiff, mid)
    high = mid-1
  } else {
    low = mid+1
  }
}

 

이제 저희는 특정한 차이값으로 탐색이 가능한지를 살펴보면 되겠다는 걸 알았습니다. 이건 어떻게 확인할까요?

아이디어는 4차이가 나는 경우를 확인하고 싶을 때, 최소값을 특정했다면 최대값의 범위를 제한할 수 있다는 겁니다.

최소값이 0이라고 할 때 차이 4를 확인하고 싶다면, 최대 4까지 가능하겠죠? 

이런식으로 [최소값 ~ 최소값 + 차이] 로 범위를 특정해서 해당 범위의 칸만 밟으면서 목적지까지 도달하는지 확인해나갈 수 있습니다.

for 문으로 최소값을 하나씩 올려가면서 그 사이의 칸들로만 도달이 가능한지 확인해볼 수 있습니다.

그리고 저희는 배열에서 나올 수 있는 최소와 최대값을 알고 있기 때문에 for문은 최소값 ~ 최대값-차이 사이만 확인하면 되겠다는 것도 알 수 있겠네요.

for min in minValue...maxValue-minDiff {
    
    guard min...min+minDiff ~= map[0][0] else { continue }
    
    var visit = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
    visit[0][0] = true
    
    var q = [Point(0, 0)]
    while !q.isEmpty {
      let curr = q.removeFirst()
      
      for d in 0..<4 where 0..<n ~= curr.r + dr[d] && 0..<n ~= curr.c + dc[d] {
        let next = Point(curr.r + dr[d], curr.c + dc[d])
        guard !visit[next.r][next.c], min...min+minDiff ~= map[next.r][next.c] else { continue }
        if next.r == n-1, next.c == n-1 {
          return true
        }
        visit[next.r][next.c] = true
        q.append(next)
      }
    }
  }

 

BFS에서 최대 최소를 특정하는 방법이 핵심이었고, 이분탐색은 꼭 이분탐색이 아니라 투포인터로도 접근해볼 수 있을 것 같습니다. :)

 

해결방법

typealias Point = (r: Int, c: Int)

let n = Int(readLine()!)!
var map = [[Int]]()

var maxValue = 0
var minValue = 200
for _ in 0..<n {
  map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
  maxValue = max(maxValue, map.last!.max()!)
  minValue = min(minValue, map.last!.min()!)
}

var minDiff = 201
var dr = [-1, 1, 0, 0]
var dc = [0, 0, 1, -1]

func search(_ minDiff: Int) -> Bool {
  
  for min in minValue...maxValue-minDiff {
    
    guard min...min+minDiff ~= map[0][0] else { continue }
    
    var visit = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
    visit[0][0] = true
    
    var q = [Point(0, 0)]
    while !q.isEmpty {
      let curr = q.removeFirst()
      
      for d in 0..<4 where 0..<n ~= curr.r + dr[d] && 0..<n ~= curr.c + dc[d] {
        let next = Point(curr.r + dr[d], curr.c + dc[d])
        guard !visit[next.r][next.c], min...min+minDiff ~= map[next.r][next.c] else { continue }
        if next.r == n-1, next.c == n-1 {
          return true
        }
        visit[next.r][next.c] = true
        q.append(next)
      }
    }
  }
  
  return false
}

var low = 0
var high = maxValue-minValue

while(low <= high) {
  let mid = (low + high)/2
  if search(mid) {
    minDiff = min(minDiff, mid)
    high = mid-1
  } else {
    low = mid+1
  }
}

print(minDiff)

 

배운점

후 쉽지 않았다.... 다른 분들의 풀이를 참고했는데 처음에 제대로 이해를 못해서 범위를 산정하는 부분에서 꼬여서 몇 번을 틀렸다 ㅠㅠ

그래도 두 번째 골1 문제다.. 이제부터 좀 높은 레벨의 문제를 많이 풀어봐야겠다.