[14699번] 관악산 등산

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

일단 이 문제에 대해 분석해보자.

1. 단방향 그래프로 변환이 가능하다.

즉, 높이가 낮은 쪽 -> 높이가 높은 쪽으로 노드를 연결시켜주면 된다.

2. 자신의 노드에 들어오는 '->'개수가 몇개인지 카운트를 한다.

카운트가 0인 노드는 결국 들어오는 '->'가 없는 출발 노드이다.

이 두가지를 이용하여 재귀를 구현해보자.

가장 말단 노드에 도착했을때 1을 리턴하며 이전 노드들에 누적을 시켜주고, 

그리고 이미 방문한 노드들에 대해 처리를 해준다.(아래 코드 참조)

처음에는 우선순위 큐로 해결하려 하였으나, n^2lgn으로 실패하였는데 생각해보니 단순 재귀를 이용하여 O(n)에 해결이 가능하다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include <iostream> #include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int height[5002]; vector<int> adj[5002]; int visit[5002]; bool indegree[5002];   int dfs(int here, int cost) {     int len = adj[here].size();       for (int i = 0; i < len; i++)     {         int there = adj[here][i];           // 이미 there이 방문한 노드면         if (visit[there] >= 2)         {             visit[here] = max(visit[here], visit[there] + 1);             continue;         }           int get = 1;         get += dfs(there, i);           // 이미 here이 방문한 노드면         if (visit[here] >= 2)             visit[here] = max(visit[here], get);         else             visit[here] = get;         }       return visit[here];     } int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 1; i <= n; i++)     {         scanf("%d", &height[i]);         visit[i] = 1;     }       for (int i = 0; i < m; i++)     {         int a, b;         scanf("%d %d", &a, &b);           // 높이가 낮은 쪽->높은 쪽으로 연결         // indegree는 진입 노드 개수 카운트         if (height[a] > height[b])         {             adj[b].push_back(a);             indegree[a] = true;         }           else         {             adj[a].push_back(b);             indegree[b] = true;         }     }       // 진입 노드가 0개라면 시작 노드가 될 수 있다.     for (int i = 1; i <= n; i++)         if (!indegree[i])             dfs(i, 1);       for (int i = 1; i <= n; i++)         printf("%d\n", visit[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus