[카카오] 외벽점검

https://youtu.be/yYc2KiCSIoA?si=UY_QFNsKxskUUjiE

 

해당 영상을 참고하여 포스팅했습니다!

 

동그란 모양의 외벽에 취약한 지점이 있다. 취약 지점을 점검하기 위해 친구들을 보내는데, 이때 점검 시간은 1시간이며 친구들 제각각 1시간동안 이동하며 점검할 수 있는 거리가 있으며 친구를 최대한 적게 보내야 하는 것이 문제의 관건이다.

 

주목해야할 것은,

1. 외벽이 원형이라 취약지점 간 거리를 구할 때 외벽 길이를 두 배로 늘려서 확인을 편리하게 하는 것

2. 어떤 취약지점을 우선 방문하느냐, 어떤 친구를 먼저 보내느냐에 따라 보내는 친구 수를 달리할 수 있다는 것

3. 친구를 보내 취약지점을 방문할 때 점검 가능한 거리를 벗어날 때 해당 지점은 방문할 수 없다는 것.

(+ 추가로 시계, 반시계 두 방향 모두 이동가능하지만, 두 경우 실상 같은 경우이므로 시계방향만 고려한다!)

 

세 가지를 최대한 고려하며 마지막으로 어떤 경우도 취약지점을 점검할 수 없는 경우 -1을 return해야 한다.

 

2번에 의해 어떤 위험 지점을 우선 방문할지(시계방향으로 이동하므로 순열로 확인하지 않고 뭐부터 시작할지 확인만 하면 된다) 확인한다. 그리고 어떤 친구를 먼저 보낼지(dist) 순열을 만들어 일일이 확인한다. weak의 길이가 최대 15라는 것, dist 역시 최대 8이라는 것을 보고 모든 경우를 다 확인하는 완전탐색에 대한 힌트를 얻을 수 있을 것이다.

 

영상에서 나온 예시로 확인해보자.

현재 최소 친구수를 MinCnt로 int.INF로 초기화시킨 상태다. 여기서 보내질 친구의 순서를 순열로 확인할 수 있으며, 처음 시작을 어떤 취약지점(weak)로 할지에 따라 보낼 친구 수를 구할 수 있다.

3번에 의해 어떤 취약지점까지는 가능하지만 그 다음 취약지점까진 가능하지 않은지 확인을 해줘야하며, 다음 취약지점까지 가능하지 않다면 다음 친구가 확인해야 할 취약지점 위치를 업데이트해주며 cnt를 하나 늘려준다!

 

예시를 보면,

첫번째 친구는 1만큼 거리를 이동할 수 있지만, 5번까지는 이동할 수 없어 1번에서 2번까지 이동하며,

두번째 친구는 2만큼 거리를 이동할 수 있지만, 10번까지는 이동할 수 없어 5부터 7까지 2만큼 거리를 이동하며,

세번째 친구는 3만큼 거리를 이동할 수 있어 10번부터 1번까지 이동할 수 있고 여기까지 보내진 친구 수는 모두 3명이다.

 

이런 식으로 모든 경우를 구하며 카운트를 세며 최소 카운트를 구한다.

 

다음은 코드 전문이다.

import itertools
import math

def solution(n, weak, dist):
    weakSize = len(weak)
    weak = weak + [w + n for w in weak]
    minCnt = math.inf
    
    for start in range(weakSize) :
        for d in itertools.permutations(dist, len(dist)) :
            cnt = 1
            pos = start
            
            for i in range(1, weakSize) :
                nextPos = start + i
                diff = weak[nextPos] - weak[pos]
                
                if diff > d[cnt-1]:
                    pos = nextPos
                    cnt += 1
                    
                    if cnt > len(dist) :
                        break
            if cnt <= len(dist) :
                minCnt = min(minCnt, cnt)
            
    if minCnt == math.inf :
        return -1
    
    return minCnt