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

programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

풀이 방법

• 어떤 친구들 먼저 처리할지 순서가 매번 다르기 때문에 permutation함수를 이용해서 dist의 모든 순서를 다 고려해준다.
• -> dist = [3, 5, 7]일 때, [3, 5, 7], [3, 7, 5], [5, 3, 7], .... 모두 고려 
• 각 dist에 대해서 dijkstra를 이용해 모든 취약점을 방문하는 최소 친구 수를 구한다.
• 그래프의 방문을 이용할 것이기 때문에 graph[i][j] = i번째 weak과 j번째 weak사이의 거리로 graph를 저장해둔다.
• dijkstra로 모든 weak를 방문하면서 이동 거리를 구하고, 현재 dist가 갈 수 있는 범위를 넘어갈 경우 다음 친구에게 넘겨준다.
• 한 번에 맞지는 못했다. 여러 번 제출한 후에 예외를 떠올리고 맞은거라 실제 시험이었다면 부분점수였을 듯 
• 카카오 문제에서 생각보다 입력값이 크다면, 모든 경우에 수에 대해 다 고려했는지 꼭 다시 한번 고민할 것
• 내가 구현한 탐색 부분에서는 첫 시작 지점과, 친구의 순서, 시작 친구가 고정이기 때문에 모든 경우의 수를 고려하기 위해서는 친구 배열 dist의 순열 전체에 대해 반복해야 한다.

전체 코드

import heapq
from itertools import permutations

def solution(n, weak, dist):
    m = len(weak)
    # 그래프처럼 탐색하기 위해 이차원 배열 graph 생성
    graph = [[0]*m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            temp = min((weak[i]-weak[j]+n)%n, (weak[j]-weak[i]+n)%n)
            graph[i][j] = temp
            graph[j][i] = temp

    answer = float('inf')
    per = list(permutations(dist, len(dist))) # dist에 대한 모든 순열 탐색 
    for k in range(len(per)):
        queue = []
        x = 0
        visited = [0]*m
        heapq.heappush(queue, (0, 0))
        i = 0
        dist_ = per[k]
        while queue:
            c, temp = heapq.heappop(queue)
            if visited[temp]: continue
            visited[temp] = 1
            if x + c > dist_[i]:
                i += 1  # 다음 친구에게 넘겨주기 
                x = 0
            else:
                x += c
            if i > len(dist) -1:
                break # 마지막 친구까지 했는데 못했을 때 -> 해당 dist에서 취약 지점을 전부 점검할 수 없는 경우 
            for j in range(m):
                heapq.heappush(queue, (graph[temp][j], j))
        else:
            answer = min(answer, i+1)
    if answer == float('inf'):
        return -1
    return answer