백준 1005번을 통한 최장거리 알고리즘과 위상정렬 소개

우선 백준 1005번을 보고 오자.

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

1005번: ACM Craft

 

이 문제에 대한 올바른 문제해결 방법은 '위상정렬' 이다.

위상정렬은 보통 어떤 작업에 순서가 정해져있을 때, 순서를 결정하기 위해 사용하는 알고리즘입니다.

예를들어 스타크래프트에서 어떤 상위 건물을 지으려면, 하위 건물들을 몇가지 지어야 하는 경우가

있는데, 이처럼 어떤 작업 진행전에 해야하는 '순서' 가 존재할시 위상정렬을 사용한다.

위상정렬을 사용하기 위한 구체적인 조건은 '사이클' 이 없는 단방향 그래프여야합니다. 위상정렬은 보통 큐, 혹은 스택으로 구현하는데 나는 큐를 사용하여 구현하겠다. 구현 방법은 아래와 같다.

1) 자신에게 들어오는 간선수=indegree가 0)인 정점을 큐에 PUSH

2) 큐의 top에 있는 정점을 하나 뽑아와 그 정점과 그정점으로부터 나오는 간선 삭제( bfs탐색하며 삭제하는 느낌)

3) 큐가 빌 때까지(모두 방문할 때 까지) 2번반복.

 

 

즉, 자신을 가르키는 노드들 중, 종료되지 않은 노드의 수를  indegree라는 값으로 표현하고,

탐색 중에 종료된 노드는 자신이 가르키는 노드의 indegree 값을 1낮추어 자신의 종료를 표시한다.

indegree==0 이 된다면, 더이상 해당 노드를 진행하기 전에 수행해야하는 '사전 작업' 이 존재하지 않는 것이므로, 해당 노드를 탐색 범위에 넣는다. 

실제 구현은 시작점에서 자신이 가르키는 모든 노드의 indegree를 1 낮추고, 만약 indegree가 0이되는 값이 존재 시, 해당 노드를 next queue에 넣는 방향으로 가면 된다. 

 

 

출처 성호스

 

즉 indegree가 0인 정점과 그 정점에서 나오는 간선들을 삭제한 뒤, 모든 정점들의 indegree를 새롭게 갱신하고

다시 indegree가 0인 정점을 찾는 과정을 반복한다. 이 과정에서, 삭제되는 정점의 값( 이 문제의 경우 시간값)을

해당 정점이 가르키는 정점에 더해준다.  ex) d>c 에서 d를 제거하고 d의 값을 c에 더한다. 

이러한 방식을 사용하면, 그래프를 처리 순서에 맞게 정렬하면서, 목표지점까지 갈때 걸리는 시간을 찾을 수 있다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n, k;
        cin >> n >> k;

        int arr[1002];
        for (int i = 1; i <= n; i++) cin >> arr[i];
        

        vector<int> adj[1002];
        int ind[1002] = { 0, };//ind[x]>> x번 정점으로 들어오는 정점수= indegree 값.
        queue<int> q;
        int result[1002];

        while (k--) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            ind[b]++;
        }

        int W;
        cin >> W;

        for (int i = 1; i <= n; i++) {
            if (ind[i] == 0) {//indeg=0 즉 시작정점들을 모두 push 
                q.push(i);
            }
            result[i] = arr[i];//자기자신 건설시간 기본값으로 추가.
        }

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (int i = 0; i < adj[cur].size(); i++) {//bfs 탐색 + 위상정렬
                int next = adj[cur][i];
                ind[next]--;
                result[next] = max(result[next], result[cur] + arr[next]);//기존 값 or 현재정점 거치는 갱신값 중 긴거리로 갱신.
                if (ind[next] == 0) {//위의 과정을 통해 indegree가 0 되면 queue에 push해 탐색
                    q.push(next);
                }
            }
        }

        cout << result[W] << endl;
    }

    return 0;
}

 

위처럼 위상정렬을 사용하지 않더라도, 다익스트라 알고리즘을 응용한 최장거리 알고리즘을 통해서도 해결이 가능하다.

아이디어는 시작건물> 목표건물 로 가기위해서는 결국 목표건물의 하위건물들을 전부 지어야하고, 이를 한번 더 생각해서 시작 건물에서 목표건물로 가는 최장경로를 찾는다면, 목표건물의 하위건물들 중 가장 늦게 완성되는 건물의 완성시간을 찾을 수 있다는 것이다. 즉 모든 시작정점> 목표정점으로 가는 최장경로들중 최소값이 가장 빨리 목표건물을 완성하는 방법이다. 하지만, 이 방식은 시간복잡도가 O(N^2) 인데 비하여, 위상 정렬은 O(V+E)로 훨씬 효율적이기에 시간복잡도를 잘 계산해봐야 했고, 이 문제의 경우 아래 코드처럼 다익스트라 사용시 시간초과가 난다. 하지만 최단거리가 아닌, 최장거리알고리즘에 대한 설명도 할겸 틀린 코드도 풀이해보도록 하겠다.

 

구현 방식은 모든 간선을 역방향으로 저장한 뒤, 도착지점에서 시작점( 들어오는 간선이 없는 정점> visit 배열값이 1로 갱신되지 않은 정점) 까지의 '최장거리' 를 다익스트라를 통해 구현한 것이다. 여기서 주의할점이

 

if (dist[now] > now_dist) continue; 

 

if (e.second+now_dist>dist[now]) 

 

 

이 두 부분인데, 난 보통 다익스트라에서 최단거리를 풀 때, '가장 짧은 길들만 우선적으로 연결하면 결국 최단거리를

완성한다' 라는 최단거리 다익스트라 알고리즘의 특성에 맞게

 

if (dist[now] !=inf) continue; 

 

if (dist[now]==inf) 

 

이렇게 구현했다. 위 코드의 의미는 '한번이라도 dist배열이갱신되었다면, 다시 갱신하지 않는다' 의 뜻으로, 어차피 우선순위 큐에서 먼저 pop 되는 큐의 top 값으로 갱신된 거리 값은 갱신될 필요가 없기에 이런식으로 구현했다. 하지만, 

최장거리는 이야기가 다른데, 아래 예시를 보자.

 

1(3)> 2(2)  >4(7)     

1(3)> 3(1)>5(8) < 4(7)

1(3) 의 의미는 1번정점의 건설비용이 3이란 뜻이다. 

1번 정점에 연결된 2,3 번 정점의 건설비용은 각각 2,1  이고 현재까진 2번 건물을 건설하는 시간은 2, 3번은 1로, 더 오래걸리는 건물은 2번이다. 하지만 2번은 바로 4번 건물을 건설하기 때문에 1>2>4 경로를 통한 총 건설시간은 3+2+7=13이고, 3번은 5번을 거쳐가야하기에 3+1+8+7로 19이다. 따라서 최단거리문제에서 pq에서 가장 짧은 간선을

뽑아서 연결해나가며 최단거리를 구하듯, 최장거리를 풀면 예외가 생긴다는 것이다.

이를 해결하고자 '한번 갱신된 거리는 어차피 최장거리가 아니니 넘어가자' 가 아닌 '새로운 dist값(이전정점까지거리+현재간선)이 기존 dist값보다 크면 갱신한다' 로 바꿔준 것이다. 매우 간단한 예시였으나, 처음 다익스트라를 배울 때 잘못배워 고생을 좀 했다... 아래는 다익스트라를 통한 코드이니 참고하자.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int max_v = 1005;
const int inf = -1;
int dist[max_v];
int visit[max_v];//시작조건 없는 위치:0 있는 위치:1
int arr[max_v];
vector<pair<int, int>> rev[max_v];//거꾸로 
vector<pair<int, int>> tmp;
vector<int> ans;
vector<int> ex;
int maxi = inf, maxi_idx = -1;
//문제 변경으로 다익스트라를 통한 풀이는 에러난다.

//최장거리!!  

void dijk(int st) {
	priority_queue<pair<int, int>> pq;
	dist[st] = 0;
	for (auto e : rev[st]) {
		pq.push({ e.second,e.first });
	}

	while (!pq.empty()) {
		
		int now = pq.top().second, now_dist = pq.top().first;
		pq.pop();
	
		if (dist[now] > now_dist) continue;

		dist[now] = now_dist;
		if (visit[now] == 0 && maxi < now_dist) {
			maxi = now_dist;
			maxi_idx = now;
		}
		//cout << now << " " << now_dist << endl;
		for (auto e : rev[now]) {
			
			if (e.second+now_dist>dist[now]) {// 최장거리는 ==inf 로하면안된다. 첫갱신= 최단거리가 아님. 
												//ex) 1,3 거리중 3이 더 길지만 1로가는 길에서 빙 둘러가며 1+1+2 이런느낌으로 3넘는 
												//새로운 루트 탐색가능.
				pq.push({ (e.second + now_dist),e.first });
			}
		}	
	}
}
int main() {
	int t,n, k,w,a,b,c;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--) {
		
		cin >> n >> k;
		for (int i = 0; i < max_v; i++) {//초기화
			rev[i] = tmp;
			visit[i] = 0;
			dist[i] = inf;
			arr[i] = 0;
			maxi = inf;
			maxi_idx = -1;
		}
		for (int i = 1; i <= n; i++) cin >> arr[i];
		
		for (int i = 0; i < k; i++) {//그래프
			cin >> a >> b;
			rev[b].push_back({ a,arr[a]});// 거꾸로 넣기.
			visit[b] = 1;//이전 지점 존재( 시작점 x )
		}
		ans = ex;
		cin >> w;//
		dijk(w);
		/*
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		cout << endl;
		*/
		if (maxi == -1)
			maxi = 0;
		cout << maxi+arr[w] << endl;
	}

}