[python] SWEA - 1251. 하나로 / 1486. 장훈이의 높은 선반

1. 하나로

문제 해결

1. 프림 + 힙큐

2. 인접리스트를 만들어 준다.

3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고

4. key 리스트를 최솟값으로 갱신해가며 결과를 더해준다.

 

🔨 인접 행렬로 하다가 몇시간 날린 것 같다. 역시 난 인접리스트를 쓰는게 편하다.

소스 코드

import heapq

for tc in range(1, 1+int(input())):
    n = int(input())
    x_location = list(map(int, input().split()))
    y_location = list(map(int, input().split()))
    tax = float(input())

    # 인접 리스트
    adj = {i: [] for i in range(n)}
    for s in range(n):
        for e in range(n):
            if s != e:
                adj[s].append([e, (x_location[s]-x_location[e])**2 + (y_location[s]-y_location[e])**2])

    # Key: 가장 큰 값들로 채운다 | 최소 가중치들을 채울 것임
    # mst: visit
    key = [float('inf')] * n
    mst = [False] * n
    pq = []

    # 시작
    key[0] = 0
    heapq.heappush(pq, (0, 0))
    result = 0

    while pq:
        # 가중치가 최소인 정점을 뽑는다.
        k, u = heapq.heappop(pq)

        # 이미 방문한 적이 있으면 skip
        if mst[u]:
            continue

        # 아니라면 방문표시와 가중치를 결과에 더해준다.
        mst[u] = True
        result += k

        # dest: 정점 u에서 갈수 있는 곳
        # w: u -> dest 의 가중치
        for dest, w in adj[u]:
            # 그 중 방문한 적이 없고 현재까지 방문했던 가중치보다 작다면
            if not mst[dest] and w < key[dest]:
                # 새로 갱신해준다.
                key[dest] = w
                heapq.heappush(pq, (w, dest))

    print('#{} {}'.format(tc, round(result*tax)))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE

SW Expert Academy

 

2. 장훈이의 높은 선반

문제 해결

1. 부분 집합을 구하는 문제

2. 포함 했냐 0, 포함하지 않았냐 1 로 재귀함수로 구현했다.

 

🔨 전에도 한번 풀었던적이 있는데 이것보다 훨씬 어렵게 푼 것 같다. 부분집합은 이 방식으로 푸는게 좋은 듯하다.

소스 코드

def power_set(idx, tot):
    global result

    if m <= tot:
        result = min(tot, result)
        return

    if idx == n:
        return

    # 선택 O
    power_set(idx+1, people[idx]+tot)

    # 선택 X
    power_set(idx+1, tot)


for tc in range(1, 1 + int(input())):
    n, m = map(int, input().split())
    people = list(map(int, input().split()))

    result = float('inf')
    power_set(0, 0)
    print('#{} {}'.format(tc, result-m))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy