[백준 / BOJ] 14938 서강그라운드

문제

출처 : www.acmicpc.net/problem/14938

14938번: 서강그라운드

예은이가 서강그라운드게임을한다. 서강그라운드는 여러지역중 하나의 지역에 낙하하여, 아이템을 먹고 서바이벌을 하는 게임이다. 예은이는 어떤 지역에 낙하해야 가장 많은 아이템을 얻을수있는지 궁금하다.

 

지역의 개수 n

각 지역을 연결하는 길 m 지역사이의 거리 l

예은이의 수색범위 m

이 주어졌을때, 얻을 수 있는 아이템의 최대 개수를 출력하면 된다.

 

풀이

플로이드와샬 혹은 다익스트라로 풀수있는데,

플로이드 와샬로 풀경우, n=100 이므로 n^3 + n^2 번 반복하고,

(모든 최단경로 구하는데 n^3 최대값 찾는데 n^2번)

다익스트라로 풀경우, r=100, n=100이므로, 100*100log100 + n^2번 반복한다.

(한번 다익스트라를 수행하는데, 간선log노드번 반복하고, 모든 노드에서 한번씩 수행시켜야하므로 100 * 100log100이다. 마찬가지로 최대값 찾는데 n^2번 반복이 필요하다)

 

플로이드 와샬보다 다익스트라가 좀더 빠르긴한데(위 계산이 맞다면 약 50배..??), 사실 뭐로풀던 둘다 굉장히 작은시간이라 크게 상관이 없기때문에, 구현이 간단하고 코드가 짧은 플로이드 와샬로 풀었다.

 

구현은,

1. 플로이드 와샬로 모든경로에 대해 최단경로를 업데이트해준다.

2. 하나의 시작노드를 잡고, 시작노드에서 (1 ~ n번 노드)까지 각각m보다 작은 거리로 이동할수있다면, num에 더해준다. (시작 노드가 바뀌면 num을  으로 바꿔줘야한다.)

 

다익스트라 구현은 위 1번과정을 다익스트라로 변경하고 노드의 개수만큼 시작노드를 중복없이 변경하며, 다익스트라를 수행하면된다.

(이걸로 풀어보진않아서 확실하진않음)

 

2번 과정을 모든 노드에대해서 반복하고 최댓값을 출력하면 답이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14938%20%EC%84%9C%EA%B0%95%EA%B7%B8%EB%9D%BC%EC%9A%B4%EB%93%9C/main.cpp

devxb/JJUNalgo