BOJ 1766 - 문제집

[이전 블로그]에서 글 옮김

링크: https://www.acmicpc.net/problem/1766

풀이

처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.

5 3

4 1

2 3

5 3

내가 생각한 이 입력의 정답은 아래와 같다.

2 4 1 5 3

1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다.
(둘 다 1개의 문제 앞에 있음)2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.

처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.

위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	void topological(int vertex, int edges){
	vector<int> adj[vertex];
	vector<int> indegree(vertex, 0);
	while(edges--){
	int s, e;
	scanf("%d %d", &s, &e);
	adj[s-1].push_back(e-1);
	indegree[e-1] += 1;
	}
	priority_queue<int, vector<int>, greater<int>> q;
	for(int i=0; i<vertex; ++i){
	if(indegree[i] == 0){
	// 들어가는 간선이 없는 노드 (시작점)
	q.push(i);
	}
	}
	while(!q.empty()){
	int node = q.top();
	q.pop();
	printf("%d ", node+1);
	for(int i=0; i<adj[node].size(); ++i){
	int nextNode = adj[node][i];
	indegree[nextNode] -= 1;
	if(indegree[nextNode] == 0) q.push(nextNode);
	}
	}
	}
	int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	topological(n, m);
	return 0;
	}

view raw boj-1766.cpp hosted with ❤ by GitHub