[PS] 백준 #21937. 작업

문제 정보

• 난이도: 실버 I
• 문제 주소: https://www.acmicpc.net/problem/21937
• 이 문제를 푼 이유: 그룹 연습 Div 2

 

문제

민상이는 자신이 해야할 작업 $N$개를 아래와 같이 작업 순서도로 그려보았다.

위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.

작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.

민상이는 오늘 반드시 끝낼 작업 $X$가 있다. 민상이가 작업 $X$ 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!

 

나의 풀이

이 문제를 읽고 다익스트라 알고리즘에서 최단 경로를 구할 때 앞에 있는 노드만 기억하면 되는 것처럼 이 문제도 앞에 있는 노드의 번호만 알면 되겠다는 생각이 들었다. 그래서 처음에는 back[100001] 배열 하나로 해결하려고 했더니, 마지막 예제의 답이 다르게 나왔다. back이 두개 이상인 경우가 있기 때문이였다. 

이를 해결하기 위해서 back을 두 개 이상일 경우 모두 저장할 수 있도록 이차원 벡터로 생성하였다. 추가로 방문 여부도 확인해서 calculate 함수를 만들어주고 나니 DFS처럼 구현이 됐다. 즉 엣지들을 모두 반대로 바꿔서 DFS나 BFS를 통해 만난 노드의 개수를 구하면 되는 문제였다. 구현이 어렵지 않아서 금방 푼 문제였다.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> back(100001);
bool isVisited[100001];

int cnt = 0;

// 사실상 DFS
void calculate(int x) {
	isVisited[x] = true;
	if (back[x].size() == 0) return;
	for (int next : back[x]) {
		if (!isVisited[next]) {
			cnt++;
			calculate(next);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m, x;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		back[b].push_back(a);
	}

	cin >> x;
	calculate(x);
	cout << cnt;
}