[백준 / BOJ] 14699 관악산 등반 - Swift

문제

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

14699번: 관악산 등산

N개의 쉼터가 있고, 쉼터둘을 연결하는 M개의 도로가 있다.

각 쉼터에는 높이가 있으며, 항상 현재쉼터보다 높은위치로만 갈수있다고할때,

각 쉼터에서 최대한으로 방문할수있는 쉼터의 갯수를 구하는 문제다.

 

풀이

전에 풀었던 Dp+DFS문제인 

욕심쟁이 판다 :  www.acmicpc.net/problem/1937 

와 비슷한 유형?의 문제라고 생각했다

 

*항상 현재 쉼터 보다 높은 쉼터로만 갈수있으므로, 단방향 간선이다 (같은높이에있는 쉼터로도 갈수없다)*

 

각 쉼터에서 시작할때마다 모든정점을 봐주면 너무 오래걸린다.

(쉼터가 5000개 간선이 100000개 있으므로, 약 5억번 반복한다고 생각함)

 

따라서 한 쉼터에서 시작했을때,

지나가는 모든 쉼터에대해서 최대로 지나갈수있는 쉼터의 갯수를 저장해줘야한다.

 

예를들어, 예제의 경우

1번 쉼터에서 시작했을때, 

 

1 -> 4 -> 3

혹은

1 -> 5

 

이 두가지 경로를 지나가게 될것이고 

1번쉼터에서 최대로 지나갈수있는 쉼터는 (자기자신을 포함하여) 총 3개이다 (1 -> 4 -> 3)

따라서

dp[1] = 3

dp[4] = 2

dp[3] = 1

로 초기화 된다.

 

다음 2번쉼터에서 탐색을 시작했을때,

1번 쉼터와 4번 쉼터로 올라가고,

이때 dp[1]과 dp[4]의 값이 각각 이미 업데이트 되어있으므로 dp[1]의 값과 dp[4]의값을 리턴하고 더이상 탐색하지않는다.

이때 dp[4]보다 dp[2]의 값이 더 크므로 dp[1] = 3 + 1(이동횟수) = 4 가 된다.

 

이런식으로 탐색 시간을 최소화 하면서 풀면된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14699%20%EA%B4%80%EC%95%85%EC%82%B0%20%EB%93%B1%EC%82%B0/main.swift

devxb/JJUNalgo