외벽 점검

💻 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60062

📖 문제 해결
주어진 데이터 개수가 적기 때문에 완전 탐색으로 접근할 수 있는 문제입니다. itertools의 permutations함수를 이용하여 점검하는 친구들의 순서의 모든 경우의 수를 계산하고, 원형인 레스토랑의 형태를 선형으로 고려하기 위해 적절하게 변형을 하여 문제를 해결하였습니다.

from itertools import permutations

def solution(n,weak,dist):

    length = len(weak)

    # 원형으로 되어 있는 것을 선형으로 변형
    for i in range(len(weak)):
        weak.append(weak[i] + n)

    # 투입할 친구의 최솟값을 찾아야 하므로 len(dist) + 1(전체 친구 수 + 1)로 초기화
    answer = len(dist) + 1

    # 모든 취약 지점들을 시작점으로 고려해보기
    for start in range(length):

        # permutations 함수로 경우의 수를 모두 계산하고
        # 경우마다 친구들을 순서대로 투입
        for friends in list(permutations(dist, len(dist))):
            count = 1

            # 해당 친구가 start 취약 지점부터 1시간 움직여 도착한 지점을 position에 저장
            position = weak[start] + friends[count-1]

            # start 취약 지점부터 모든 취약 지점을 확인
            for index in range(start, start + length):

                # 해당 친구가 weak[index]를 지나지는 못했을 경우
                if position < weak[index]:
                    count += 1

                    # 만약 모든 친구들이 투입되었음에도 모든 취약 지점을 점검하지 못하였다면
                    if count > len(dist):
                        break

                    # 다음 친구가 weak[index]를 시작으로 취약 지점을 점검하도록 함
                    position = weak[index] + friends[count-1]

            # 최솟값 계산
            answer = min(answer,count)

    # 만약 모든 취약 지점을 점검하지 못하였다면
    if answer > len(dist):
        return -1

    return answer