문제 링크

문제 풀이 아이디어

완전탐색

주어진 친구들의 이동 거리 및 취약 지점의 위치에 일정한 규칙이 없습니다. 일단은 모든 케이스를 따져봐야 합니다. 따라서 기본적인 문제 풀이 방법은 완전탐색입니다.

하지만 무작정 완전 탐색을 하면 시간초과가 날 수 있습니다. 분기가 상당히 많이 발생할 수 있기 때문입니다. 따라서 몇가지 테크닉을 사용해서 최대한 실행시간을 줄여 봅시다.

이동거리가 먼 순서로 정렬

일단 친구들을 이동거리가 먼 순서대로 정렬합니다. 일종의 그리디 알고리즘을 활용하는 것인데요. 이동 거리가 긴 친구들부터 탐색하는 것이 최대한 적은 친구들을 가지고 외벽을 점검할 수 있기 때문입니다.

취약 지점에서 시작

문제에 의하면 친구들을 모든 지점에서 심지어 예시에서 처럼 두 지점의 사이에서 이동을 시작할 수 있습니다. 하지만 모든 지점에서 출발하는 경우를 모두 탐색하면 0개의 취약지점을 점검하는 케이스 등 고려하지 않아도 될 케이스가 많이 나올 수 있습니다. 따라서 친구들의 출발 지점은 취약지점으로 합니다.

시계 방향 only

문제에 의하면 친구들은 외벽을 시계방향으로도 그리고 반시계방향으로도 돌 수 있습니다. 하지만 두 케이스를 모두 탐색할 필요는 없습니다. a ~ b를 시계방향으로 이동하는 것은 b ~ a를 반시계방향으로 이동하는 것과 동일합니다. 따라서 시계방향으로 회전하는 경우만 탐색해도 문제 없습니다.

Set을 활용

이제 대략 어떻게 탐색할 지 윤곽이 나왔습니다. 이동거리가 먼 친구부터 탐색합니다. 그 친구가 취약 지점에서 각각 시계방향으로 이동하는 케이스를 탐색합니다. 그리고 남은 취약지점들에서 다시 2번째로 이동거리가 먼 친구가 탐색을 시작하면 됩니다.

bfs를 사용하면 구현할 수 있는데요. 우리는 bfs를 Queue 대신에 Set을 활용해서 시간을 줄일 수 있습니다. 우리가 구하고자 하는 것은 이동시켜야 하는 친구들의 최솟값입니다. 따라서 그래프 탐색의 관점에서 보면 “깊이”에만 중점을 두어서 탐색하면 되는 것이죠.

따라서 Queue 대신에 각 깊이 (= 이 문제에서는 친구)마다 새로운 Set을 활용해서 탐색하는 방법을 사용합시다. 이렇게 되면 중복되는 케이스들을 또 탐색하는 시간을 절약할 수 있습니다.

탈출 조건

위에서 언급했듯이 우리가 구하는 것은 필요한 친구들의 최소 명수입니다. bfs를 활용해서 탐색하므로 앞선 탐색은 무조건 나중 탐색보다 “얕은 깊이”, 즉 필요한 친구들의 수가 적습니다.

따라서 더 이상 남은 취약지점이 같다면 현재까지 탐색하는데 필요했던 친구들의 명수를 바로 리턴해주면 됩니다.

코드

func solution(_ n:Int, _ weak:[Int], _ dist:[Int]) -> Int {
 
    // 이동거리가 먼 순서대로 정렬
    let dist = dist.sorted(by: >)
    // 중복을 방지하기 위해서 Set
    var set = Set<[Int]>()
    set.insert(weak)
    
    // 모든 친구들 완전 탐색
    for i in 0..<dist.count {
        let d = dist[i]
        // "깊이" 별로 탐색하기 위해서 별도 Set에 다음 경로 insert
        var newSet = Set<[Int]>()
        // "남은 취약 지점들" 완전 탐색
        for weak in set {
            // "각각 취약 지점에서 시계방향 탐색"
            for w in weak {
                let start = w
                let end = (start + d) % n
                // 탐색 된 지점은 제외
                let newWeak = weak.filter { !(start < end ? (start...end) ~= $0 : $0 <= end || start...n ~= $0) }
                // 모든 취약 지점을 탐색했다면 return
                if newWeak.isEmpty { return i + 1 }
                newSet.insert(newWeak)
            }
        }
        // 다음 "깊이"를 탐색
        set = newSet
    }

    // 완전탐색에도 불구하고 정답이 없으면 -1 리텀
    return -1
}