[백준] 14938 서강그라운드 (파이썬)

골드 Ⅳ

https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

📄 문제

• 서강그라운드는 여러 지역 중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다.
• 예은이는 낙하산에서 떨어질 때 각 지역에 아이템들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만
• 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.
• 각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다.

 

예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

 

---

💡 아이디어

• 각 지역에서 다른 지역까지의 최소 거리를 구한다. (다익스트라 알고리즘)
• 특정 지역에서 최소 거리가 m이하인 지역의 아이템을 모두 더한다.
• 각 지역에서 습득 가능한 아이템의 개수를 구한다.
• 모든 지역을 비교하여 얻을 수 있는 아이템의 최대 개수를 구한다.

 

반응형

 

📝 문제 풀이 (Code)

다익스트라 알고리즘

import sys, heapq
input = sys.stdin.readline

def dijkstra(start):
    # 최소 거리, 위치
    heap = [(0, start)]
    visited[start] = 0
    # 범위 내 지역 저장
    getItem.add(start)

    while heap:
        dist, curr = heapq.heappop(heap)

        if visited[curr] < dist:
            continue
        # 인접한 지역 탐색
        for next, d in graph[curr]:
            # 다음 지역까지의 이동 거리
            sumDist = dist + d
            # 수색 범위 안에 들어오거나 저장된 거리보다 짧으면
            if sumDist < visited[next]:
                # 최소 거리 갱신 
                visited[next] = sumDist
                # 수색 범위 내 지역 추가
                getItem.add(next)
                # 추가 탐색
                heapq.heappush(heap,(sumDist, next))


n, m, r = map(int, input().split())
# 지역 번호와 인덱스 맞추기
items = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
for _ in range(r):
    a, b, l = map(int, input().split())
    graph[a].append((b, l))
    graph[b].append((a, l))

# 아이템 최대 개수 저장
ans = 0
for i in range(1,n+1):
    # 범위 내 지역
    getItem = set()
    # 최소 거리 저장
    visited = [m+1]*(n+1)
    # i 지역에서 다른 지역까지의 최소 거리 찾기
    dijkstra(i)
    # i 지역에서 습득 가능한 아이템 개수 저장
    totalItems = 0
    for j in getItem:
        totalItems += items[j]
    # 아이템 최대 개수 갱신
    ans = max(ans, totalItems)
print(ans)

 

플루이드 워셜 알고리즘

모든 지역에서 최소거리를 찾아야하므로 플루이드 워셜 알고리즘 사용할 수 있다.

import sys
input = sys.stdin.readline

n, m, r = map(int, input().split())
# 지역 번호와 인덱스 맞추기
items = [0] + list(map(int, input().split()))
# 수색 범위+1 거리로 초기화
graph = [[m+1] * (n + 1) for _ in range(n + 1)]
# 각 간선에 대한 정보를 입력 받아, 그 값으로 거리 초기화
for _ in range(r):
    # a에서 b로 가는 거리 l
    a, b, l = map(int, input().split())
    graph[a][b] = l
    graph[b][a] = l

# 자기 자신으로 가는 거리는 0으로 초기화
for i in range(n + 1):
    graph[i][i] = 0

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 0
# 저장한 최댓값을 출력
for x in range(1, n + 1):
    # x 지역에서 습득 가능한 아이템 개수 저장
    totalItems = 0
    for y in range(1, n + 1):
        if graph[x][y] <= m:
            totalItems += items[y]
    # 최대 아이템 개수 갱신
    ans = max(ans, totalItems)
print(ans)