[CLASS 4]백준 14938번 - 서강그라운드

14938번 : 서강그라운드

 

 

가장 먼저 든 생각은 플로이드 와샬 알고리즘이었다. 구현이 쉽기도 하고 지역의 개수가 최대 100개라 O(V^3)으로도 풀릴까? 라는 생각에 먼저 플로이드 와샬로 구현해 보았다.

 

내 코드(플로이드 와샬):

# dawitblog.tistory.com/166
import sys
input = sys.stdin.readline
INF = sys.maxsize

# 입력
n,m,r = map(int,input().split())
items = list(map(int,input().split()))
roads = [[INF]*n for _ in range(n)]
for _ in range(r):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1

    roads[a][b] = roads[b][a] = c

# 플로이드 와샬
for v in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                roads[a][b] = min(roads[a][b],roads[a][v] + roads[v][b])

# 각 지점에서 얻을 수 있는 아이템
costs = []
for start in range(n):
    dest = [end for end in range(n) if roads[start][end] <= m]
    item = 0
    for end in dest:
        item += items[end]
    costs.append(items[start]+item)

# 출력
print(max(costs))

 

잘 돌아간다. 백준에서도 정답처리 받았다. 하나 아쉬운 점은 시간 복잡도가 O(V^3) 이라는 점이다. n이 최대 100이라 망정이지 실제로는 못써먹을 코드다.

 

이를 개선하기 위해 다익스트라로 다시 풀었다. 사실 이 문제는 모든 정점에서 다른 모든 정점까지의 거리를 구하는 문제이기 때문에 플로이드 와샬이 더 어울린다고 생각하지만, 시간복잡도를 생각해서 다익스트라로도 풀었다.

 

내 코드(다익스트라):

# dawitblog.tistory.com/166
import sys
from heapq import heappush,heappop
input = sys.stdin.readline
INF = sys.maxsize

# 다익스트라
def dijkstra(start, distance):
    hq = []
    heappush(hq,(0,start))
    distance[start] = 0

    while hq:
        dist , now = heappop(hq)

        if distance[now] < dist:
            continue

        for new in roads[now]:
            cost = dist + new[1]

            if cost < distance[new[0]]:
                distance[new[0]] = cost
                heappush(hq,(cost,new[0]))

    return distance

# 입력
n,m,r = map(int,input().split())
items = list(map(int,input().split()))
roads = [[] for _ in range(n)]
for _ in range(r):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1

    roads[a].append((b,c))
    roads[b].append((a,c))

# 각 지점에서 얻을 수 있는 아이템
max_items = 0
for start in range(n):
    item = 0
    for dest,dist in enumerate(dijkstra(start,[INF]*n)):
        if dist <= m:
            item += items[dest]
    
    max_items = max(max_items,item)

# 출력
print(max_items)

 

시간 복잡도는 O(V^3) 에서 O(V^2logV)로 줄었다. 백준에서도 시간이 1/7 가량으로 줄었다.