백준 1939 중량제한

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

분류: 이분 탐색

---

접근방식

하 이번 문제도 너무 어려웠습니다... 설명이 애매해서 이해도 어려웠고 메모리제한............ ㅂㄷㅂㄷ

먼저 문제의 마지막에 

" 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. "

라고 되어있어서 마지막에 주어진  두 섬으로 한 번에 가는 경우를 체크하는건가? 그럼 중간에 경로들은 왜 주어진거지? 문제가 좀 이상한데? 라고 생각했었습니다. 

결국 여기서 말하는 한 번의 이동이란 처음 섬에서 특정 중량으로 출발시킨 짐이  목표 섬까지 도착하는 경로를 의미합니다.

 

중량을 기준으로 이분 탐색을 해서 각 중량으로 이동이 가능한지 체크해서 해결했습니다.

var mostWeight = 0
while low <= high {
    let mid = (low + high)/2

    if canMove(for: mid) {
        mostWeight = mid
        low = mid+1
    } else {
        high = mid-1
    }
}

이동이 가능한지는 제한 무게보다 크거나 같은지 체크하면서 bfs를 돌렸습니다.

func canMove(for weight: Int) -> Bool {
    var visited = Set<Int>([ab[0]])
    var q: [Int] = [ab[0]]
    
    while !q.isEmpty {
        let curr = q.removeFirst()
        for (island, w) in islands[curr] where w >= weight {
            if island == ab[1] {
                return true
            }
            guard !visited.contains(island) else { continue }
            visited.insert(island)
            q.append(island)
        }
    }
    return false
}

 

마지막 난관은 메모리 제한이었는데.....

bfs에서 queue를 써야하다 보니까 시간을 의식해서 더블스택 큐를 만들어서 사용했는데, 여기서 배열을 많이 생성해서 사용핟보니 메모리 제한에 걸렸던 것 같습니다. 어차피 이분 탐색은 탐색을 그렇게 많이 하지 않기 때문에 그냥 array의 removeFirst 사용해서 통과했습니다 ㅠㅠ

 

해결방법

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
var islands = [[(Int, Int)]](repeating: [], count: nm[0]+1)

var low = 0
var high = 0

for _ in 0..<nm[1] {
    let abc = readLine()!.split(separator: " ").map { Int(String($0))! }
    islands[abc[0]].append((abc[1], abc[2]))
    islands[abc[1]].append((abc[0], abc[2]))
    high = max(high, abc[2])
}
let ab = readLine()!.split(separator: " ").map { Int(String($0))! }

var mostWeight = 0
while low <= high {
    let mid = (low + high)/2

    if canMove(for: mid) {
        mostWeight = mid
        low = mid+1
    } else {
        high = mid-1
    }
}

func canMove(for weight: Int) -> Bool {
    var visited = Set<Int>([ab[0]])
    var q: [Int] = [ab[0]]
    
    while !q.isEmpty {
        let curr = q.removeFirst()
        for (island, w) in islands[curr] where w >= weight {
            if island == ab[1] {
                return true
            }
            guard !visited.contains(island) else { continue }
            visited.insert(island)
            q.append(island)
        }
    }
    return false
}

print(mostWeight)

 

배운점

풀이 자체보다도 이해가 어려웠던 문제였다!!!!! 그리고 메모리 제한..... 후 너무 고통스러웠다 ㅠㅠ