[프로그래머스] 외벽 점검

문제 요약

길이가 n인 원형 외벽에 여러 개의 취약 지점이 있다.

각 친구는 1시간 동안 이동할 수 있는 거리가 서로 다르며, 취약 지점 중 원하는 곳에서 출발해 시계 방향이나 반시계 방향으로 이동할 수 있다.

모든 취약 지점을 점검하기 위해 필요한 친구 수의 최솟값을 구해야 한다.

모든 친구를 투입해도 전체 취약 지점을 점검할 수 없다면 -1을 반환한다.

핵심 아이디어

이 문제에서 어려운 점은 외벽이 원형이라는 것이다.

원형에서는 마지막 취약 지점 다음에 첫 번째 취약 지점이 이어지므로, 일반적인 일차원 배열처럼 처리하기 어렵다.

따라서 취약 지점 배열을 두 배로 늘려 원형 외벽을 일자로 펼친다.

예를 들어 다음과 같은 입력이 있다고 하자.

n = 12
weak = [1, 5, 6, 10]

각 취약 지점에 외벽 길이 n을 더한 값을 뒤에 붙인다.

[1, 5, 6, 10, 13, 17, 18, 22]

이제 10번 지점부터 점검을 시작하는 경우도 다음과 같은 연속된 구간으로 표현할 수 있다.

10 -> 13(1) -> 17(5) -> 18(6)

괄호 안의 숫자는 원래 원형 외벽에서의 위치다.

원형을 일자로 펼친 뒤에는 다음 두 가지를 모두 확인한다.

어떤 취약 지점부터 점검을 시작할 것인가
친구들을 어떤 순서로 투입할 것인가

친구의 수는 최대 8명이므로 모든 친구의 투입 순서를 순열로 확인할 수 있다.

풀이 과정

1. 원형 외벽을 일자로 펼치기

기존 취약 지점에 n을 더한 값을 배열 뒤에 붙인다.

extended_weak = weak + [position + n for position in weak]

취약 지점의 개수가 4개라면 확장된 배열의 길이는 8이 된다.

2. 점검 시작 위치 선택

모든 취약 지점이 점검 시작 위치가 될 수 있다.

for start in range(weak_count):

start에서 시작해 취약 지점의 개수만큼 확인하면 원형 외벽을 정확히 한 바퀴 점검하게 된다.

range(start, start + weak_count)

3. 친구들의 투입 순서 만들기

이동 거리가 긴 친구를 먼저 투입하는 것이 항상 최적이라고 보장할 수는 없다.

친구마다 시작 위치가 달라질 수 있기 때문에 친구들의 모든 투입 순서를 확인해야 한다.

for friends in permutations(dist):

4. 첫 번째 친구 투입

첫 번째 친구는 현재 시작 취약 지점에서 출발한다.

friend_count = 1
coverage = extended_weak[start] + friends[0]

coverage는 현재 친구가 점검할 수 있는 마지막 위치다.

5. 점검 범위를 벗어나면 다음 친구 투입

현재 취약 지점이 coverage보다 크다면 현재 친구가 그 지점까지 이동할 수 없다는 의미다.

if extended_weak[index] > coverage:

다음 친구를 해당 취약 지점에서 출발시킨다.

friend_count += 1
coverage = extended_weak[index] + friends[friend_count - 1]

6. 최소 친구 수 갱신

한 가지 시작 위치와 친구 순서에 대한 점검이 끝나면 최소 친구 수를 갱신한다.

answer = min(answer, friend_count)

모든 경우를 확인한 뒤에도 answer가 전체 친구 수보다 크다면 점검이 불가능한 경우다.

if answer > len(dist):
    return -1

Python 코드

from itertools import permutations


def solution(n, weak, dist):
    weak_count = len(weak)

    # 원형 외벽을 일자로 펼친다.
    extended_weak = weak + [position + n for position in weak]

    # 친구를 모두 사용한 것보다 큰 값으로 초기화한다.
    answer = len(dist) + 1

    # 점검을 시작할 취약 지점을 선택한다.
    for start in range(weak_count):

        # 친구를 투입하는 모든 순서를 확인한다.
        for friends in permutations(dist):
            friend_count = 1

            # 첫 번째 친구가 점검할 수 있는 마지막 위치
            coverage = extended_weak[start] + friends[0]

            # 시작 지점부터 취약 지점의 개수만큼 확인한다.
            for index in range(start, start + weak_count):

                # 현재 친구가 해당 취약 지점에 도달할 수 없는 경우
                if extended_weak[index] > coverage:
                    friend_count += 1

                    # 모든 친구를 사용해도 부족하다면 탐색을 중단한다.
                    if friend_count > len(dist):
                        break

                    # 다음 친구를 현재 취약 지점부터 투입한다.
                    coverage = (
                        extended_weak[index]
                        + friends[friend_count - 1]
                    )

            answer = min(answer, friend_count)

    if answer > len(dist):
        return -1

    return answer

코드 설명

원형 배열 확장

extended_weak = weak + [position + n for position in weak]

원형 외벽의 시작과 끝이 연결되는 상황을 일차원 배열의 연속된 구간으로 바꾼다.

이렇게 하면 각 취약 지점을 시작점으로 선택한 뒤, 오른쪽 방향으로 취약 지점의 개수만큼만 확인하면 된다.

문제에서는 시계 방향과 반시계 방향 이동을 모두 허용한다.

하지만 반시계 방향으로 점검하는 구간도 그 구간의 반대쪽 취약 지점을 시작점으로 선택하면 시계 방향 탐색으로 표현할 수 있다. 모든 취약 지점을 시작점으로 확인하므로 한 방향만 탐색해도 된다.

친구 순열

for friends in permutations(dist):

친구들의 이동 거리가 다음과 같다면,

[1, 2, 3]

다음과 같은 모든 투입 순서를 확인한다.

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

친구의 수가 최대 8명이므로 순열의 최대 개수는 다음과 같다.

8! = 40,320

제한 범위 안에서 충분히 탐색할 수 있다.

현재 친구의 점검 범위

coverage = extended_weak[start] + friends[0]

친구가 start 위치에서 출발하고 이동 가능 거리가 friends[0]이라면 coverage까지 점검할 수 있다.

취약 지점의 위치가 coverage 이하라면 같은 친구가 계속 점검한다.

다음 친구 투입

if extended_weak[index] > coverage:

현재 친구의 이동 범위를 벗어난 첫 번째 취약 지점에서 다음 친구가 출발한다.

친구는 취약 지점이 아닌 위치에서도 출발할 수 있지만, 점검해야 할 지점보다 앞에서 출발하면 이동 거리만 낭비하게 된다. 따라서 아직 점검하지 않은 첫 취약 지점에서 출발시키는 것이 가장 유리하다.

점검할 수 없는 경우

if friend_count > len(dist):
    break

사용할 수 있는 친구 수보다 더 많은 친구가 필요하다면 현재 시작점과 투입 순서로는 점검할 수 없다.

해당 경우의 탐색을 즉시 중단하고 다음 경우를 확인한다.

예시

다음 입력을 살펴보자.

n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]

친구를 다음과 같이 투입할 수 있다.

이동 거리 4인 친구: 5번 지점에서 출발해 5, 6번 지점 점검
이동 거리 3인 친구: 10번 지점에서 출발해 10번 지점을 점검한 뒤,
                     원형 외벽을 지나 1번 지점까지 점검

전체 취약 지점을 점검하는 데 필요한 최소 친구 수는 2명이다.

시간 복잡도

취약 지점의 개수를 W, 친구의 수를 D라고 하자.

각 취약 지점을 시작점으로 선택하고, 친구들의 모든 순열마다 최대 W개의 취약 지점을 확인한다.

O(W × D! × W)

즉, 다음과 같이 표현할 수 있다.

O(W² × D!)

W는 최대 15, D는 최대 8이므로 완전탐색이 가능하다.

공간 복잡도

원형 외벽을 일자로 펼치기 위해 취약 지점 배열을 두 배로 확장한다.

친구의 순열 하나도 추가로 사용한다.

O(W + D)

정리

이 문제는 원형 구조를 일자로 펼친 뒤 모든 시작 위치와 친구의 투입 순서를 확인하는 완전탐색 문제다.

풀이 흐름은 다음과 같다.

취약 지점 배열을 두 배로 확장
모든 취약 지점을 시작 위치로 선택
친구들의 모든 투입 순서를 순열로 생성
현재 친구의 범위를 벗어나면 다음 친구 투입
필요한 친구 수의 최솟값 계산

원형 배열을 일자로 바꾸는 아이디어와 입력 크기를 보고 순열 완전탐색이 가능하다는 것을 판단하는 것이 핵심이다.