[이코테 Ch12-14] 외벽 점검 (구현)

👩🏻‍💻문제설명

[이코테 Ch12-14] 외벽 점검 (구현)

✍️Idea Sketch

문제 요약

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

weak : 반드시 방문해야하는 지점
dist : 한번에 이동할 수 있는 거리

제한사항

• n은 1 이상 200 이하인 자연수

• weak의 길이는 1 이상 15 이하

• weak의 원소는 0 이상 n - 1 이하인 정수

• dist의 길이는 1 이상 8 이하

• dist의 원소는 1 이상 100 이하인 자연수

• weak를 모두 방문할 수 없는 경우, return -1

시간복잡도 : O(n!), 알고리즘 : 브루트포스 (완전 탐색)

처음에는 그리디로 접근하려 했다. 하지만, weak와 dist 배열의 길이가 매우 작아 완전 탐색도 고려해볼만 하다. 친구의 수가 최대 8명이므로 이들의 투입 순서를 정하는 모든 경우의 수는 8!, 약 40000이다. (순열)

친구 투입 순서를 정했으니, 첫번째 친구를 어느 취약지점에 투입시킬지 (출발 지점) 정하면 된다. 그런데 무조건 weak의 배열 순서대로 방문하면, 0m을 가로질러 여러 지점을 방문하는 경우를 고려할 수 없다. 따라서 모든 취약지점이 출발지가 될 수 있다.

취약점은 최대 15개이므로 시간복잡도는 약 40000 * 15 이다.

시간복잡도는 가장 높은 차수의 항만을 표시하는 것이 약속이므로 O(n!)이다.

중요 아이디어

1. 완전탐색
2. 외벽 확장

✍️내 소스코드

• graph : 0m 지점으로 다시 돌아오는 경우를 고려하여 weak를 n * 2로 확장한다.
• permutations : 친구를 투입하는 순서를 구한다. (순열)
• start와 for문 : 모든 취약지점은 출발지점이 될 수 있다.

  from itertools import permutations


  def solution(n, weak, dist):
      W, D = len(weak), len(dist)
      graph = weak + [w + n for w in weak]  # weak 배열 2배 확장 (0m로 돌아오는 경우)
      res = float('inf')

      for friends in permutations(dist):  # 투입 순서 (순열)
          for start in range(W):  # 첫번째 투입 index
              end = start - 1 + W  # weak 확장했으므로 + W

              p = graph[start]
              cnt = 1

              for friend in friends:
                  p += friend

                  if p < graph[end]:
                      cnt += 1

                      for x in graph:
                          if p < x:
                              p = x
                              break

                  else:
                      res = min(res, cnt)
                      break

      if res == float('inf'):
          return -1
      else:
          return res