백준 - 14938번 서강드라운드 문제풀이 [Hellfer]

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

14938번: 서강그라운드

🔷 알고리즘 분류 - 깊이 우선 탐색, 플로이드 - 워셜

난이도 - 골드 4

플로이드-워셜 알고리즘은 그래프에서 모든 노드 간의 최단 거리를 찾는 알고리즘입니다. 

 

이 알고리즘은 가중치가 있는 방향 그래프와 가중치가 있는 무방향 그래프에서 모두 사용할 수 있습니다. 

 

또한 음의 가중치를 갖는 간선이 있어도 적용할 수 있지만, 음의 사이클이 있으면 안 됩니다.

플로이드-워셜 알고리즘은 다이내믹 프로그래밍 기법을 이용합니다. 

 

이 알고리즘은 그래프의 각 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 계산합니다. 

 

이때, 한 노드를 거쳐 가는 모든 경우를 고려하므로 모든 노드 간의 최단 거리를 찾을 수 있습니다.

플로이드-워셜 알고리즘의 시간 복잡도는 O(N^3)으로, 노드의 개수가 N일 때 N^3의 연산이 필요합니다. 

 

따라서 노드의 개수가 많지 않은 그래프에서 이 알고리즘을 사용하는 것이 적절합니다.

플로이드-워셜 알고리즘은 다음과 같은 순서로 진행합니다:

1. 먼저 모든 노드의 거리를 '무한대'로 초기화하고, 자기 자신으로의 거리는 0으로 설정합니다.

2. 그래프의 간선 정보를 이용하여 노드 간의 거리를 갱신합니다.

3. 모든 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 갱신합니다.

 

이때, i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 거리보다 크다면 i에서 j로 가는 거리를 i에서 k를 거쳐 j로 가는 거리로 갱신합니다.

 

이 과정을 모든 노드에 대해 반복합니다.

🔶문제 풀이 - 플로이드 워셜을 이용한 풀이

import sys
input=sys.stdin.readline

INF=float('inf') # 무한을 의미하는 값으로 초기화

# 지역의 수(n), 수색 범위(m), 경로의 수(v)를 입력받습니다.
n,m,v=map(int,input().split())

# 각 지역에서 얻을 수 있는 아이템의 수를 입력받습니다.
# 리스트의 인덱스가 지역의 번호와 일치하도록 앞에 0을 추가합니다.
visited=[0]+list(map(int,input().split()))

# 2차원 리스트(그래프)를 만들고, 모든 값을 무한으로 초기화합니다.
graph=[[INF]*(n+1) for _ in range(n+1)]

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화합니다.
for _ in range(v):
    x,y,z=map(int,input().split())
    graph[x][y]=z
    graph[y][x]=z

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화합니다.
for i in range(1,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])

# 각 지역에서 수색 범위 내에 있는 지역의 아이템을 모두 합한 값을 구하고, 그 중 최대값을 찾습니다.
result=0
for i in range(1,n+1):
    count=0
    for j in range(1,n+1):
        if graph[i][j]<=m:
            count+=visited[j]
    result=max(result,count)
            
# 결과를 출력합니다.
print(result)

🔶문제 이해하기

아래와 같은 입력값이 있다고 가정해 보겠습니다.

 

입력:
4 5 4
1 2 3 4
1 2 3
2 3 3
3 4 1
4 1 5

 

위의 입력은 4개의 지역이 있고, 수색 가능 범위가 5이며, 4개의 경로가 있다는 것을 의미합니다.

각 지역에서 얻을 수 있는 아이템의 수는 각각 3, 3, 1, 5개입니다.

그리고 각 경로의 정보는 다음과 같습니다.

1번 지역에서 2번 지역까지의 거리는 3입니다.

2번 지역에서 3번 지역까지의 거리는 3입니다.

 

3번 지역에서 4번 지역까지의 거리는 1입니다.

4번 지역에서 1번 지역까지의 거리는 5입니다.

이때, 1번 지역에서 출발하여 수색 범위 5 내에 있는 지역을 모두 방문하면, 1번 지역에서 얻을 수 있는 아이템 1개와 2번 지역에서 얻을 수 있는 아이템 2개, 총 3개의 아이템을 얻을 수 있습니다.

하지만 3번 지역에서 출발하여 수색 범위 5 내에 있는 지역을 모두 방문하면, 3번 지역에서 얻을 수 있는 아이템 3개와 4번 지역에서 얻을 수 있는 아이템 4개, 총 7개의 아이템을 얻을 수 있습니다.

따라서 최대 아이템 수는 7개이며, 출력 결과는 7이 됩니다.