[G5] 백준 33851번 DAG LCA C++ 너비 우선 탐색, 방향 비순환 그래프

리뷰

 

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

두 정점 u, v가 주어질 때 해당 정점으로 모두 이동이 가능한 정점 중 최단 거리를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 길이를 정의할 상수 변수
• n : 정점의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• edges : 인접 리스트를 저장할 벡터 배열

 

함수

1. bfs

vector<int> bfs(int sn) {
	queue<int> q;
	q.push(sn);
	vector<int> dist(n + 1, -1);
	dist[sn] = 0;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		//cout << "cn : " << cn << "\n";

		for (int nn : edges[cn]) {
			if (dist[nn] == -1) {
				dist[nn] = dist[cn] + 1;
				q.push(nn);
			}
		}
	}
	return dist;
}

 

매개변수로 받은 sn번 노드에서 모든 노드로 갈 수 있는 거리를 구하는 구하는 함수

 

 

문제풀이

1. n, m, q값을 입력 받고, m개의 간선 정보를 입력 받아 인접 리스트를 추가해 준다.
2. q번의 while루프를 수행하고, 매 루프마다 변수 u, v에 노드의 번호를 각각 입력 받아준다.
3. bfs함수에 u를 전달하여 벡터 u_dist에 리턴값을 저장해 주고, v를 전달하여 v_dist에 리턴값을 저장해 준다.
4. bfs함수는 매개변수로 sn을 받고, 정수형 큐 q를 초기화 및 sn을 push해준다.
5. 벡터 dist를 n+1크기로, 값을 -1로 저장해 준다, dist[sn] = 0으로 저장해 준다.
6. q가 빌때까지 while루프를 수행하고, 매 루프마다 q에서 원소를 한개씩 꺼내어 변수 cn에 저장해 준다.
7. cn의 인접 리스트를 순회하고, 인접한 각 노드 번호를 nn으로 저장해 준다.
8. dist[nn]이 -1일 경우 dist[nn]을 dist[cn]+1로 저장해 주고, q에 nn을 push해준다.
9. while루프가 종료된 후 dist를 리턴해 준다.
10. 변수 res를 매우 큰 값으로 초기화 하고, 1~n번 노드를 순회해 준다.
11. u_dist[i]와 v_dist[i]중 -1이 존재한다면 continue를 수행해 준다.
12. 둘 다 -1이 아니라면 res에 u_dist[i], v_dist[i]중 큰 값과 res를 비교해 더 작은 값을 res로 저장해 준다.
13. 변수 ans를 res가 초깃값이라면 -1을, 아니라면 res로 저장 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. DAG이기 때문에 인접 리스트는 단방향으로 추가해 주어야 한다.
2. 모든 정점에서 u, v로가 아닌 u, v에서 모든 정점으로의 이동 경로를 구할 것이기 때문에 인접 리스트에 방향을 거꾸로 삽입해 주어야 한다.
3. u, v에서 모든 노드로 출발해서 둘 다 갈 수 있는 정점 중 최단 거리를 구해주면 된다.

 

정답 코드

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

const int N = 2e3 + 1;
int n, m, q;
vector<int> edges[N];

vector<int> bfs(int sn) {
	queue<int> q;
	q.push(sn);
	vector<int> dist(n + 1, -1);
	dist[sn] = 0;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		//cout << "cn : " << cn << "\n";

		for (int nn : edges[cn]) {
			if (dist[nn] == -1) {
				dist[nn] = dist[cn] + 1;
				q.push(nn);
			}
		}
	}
	return dist;
}

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

	cin >> n >> m >> q;
	while (m--) {
		int u, v; cin >> u >> v;
		edges[v].push_back(u);
	}

	while (q--) {
		int u, v; cin >> u >> v;
		vector<int> u_dist = bfs(u);
		vector<int> v_dist = bfs(v);

		int res = 2e9;
		for (int i = 1; i <= n; ++i) {
			//cout << "i : " << i << " " << u_dist[i] << " " << v_dist[i] << "\n";
			if (u_dist[i] == -1) continue;
			if (v_dist[i] == -1) continue;
			res = min(res, max(u_dist[i], v_dist[i]));
		}
		int ans = res == 2e9 ? -1 : res;
		cout << ans << "\n";
	}
}