[G4] 백준 15971번 두 로봇 C++ 너비 우선 탐색

리뷰

 

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

로봇 두개가 만나 통신하기까지 이동한 거리의 합이 최소를 만들기 위한 문제

 

 

전역 변수

• N : 노드 관련 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• r1, r2 : 로봇 1, 2가 위치한 노드 번호를 저장할 변수
• v : 방문 여부를 체크할 배열
• Edge : 간선 정보를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터 배열
• Pos : 현재 위치, 누적 이동 거리, 최대 간선 길이를 정의할 구조체

 

함수

1. bfs

int bfs() {
	queue<Pos> q;
	q.push({ r1, 0, 0 });
	v[r1] = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cn = pos.cn, cv = pos.cv, mv = pos.mv;
		if (cn == r2) return cv - mv;
		//cout << "cn: " << cn << "\n";

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = edge.nv;
			if (v[nn]) continue;
			v[nn] = true;
			q.push({ nn, cv + nv, max(mv, nv)});
		}
	}
	return -1;
}

 

너비 우선 탐색을 통해 두 로봇이 통신할 수 있기까지 이동한 거리의 최소합을 구하는 함수

 

문제풀이

1. n, r1, r2에 값을 입력 받고, 변수 m을 n - 1로 저장해 준다.
2. m개의 간선 정보를 입력 받아 edges에 양방향 간선으로 추가해 준다.
3. bfs함수를 호출해 준다.
4. Pos타입의 큐 q를 초기화 하고, 초기 노드 번호를 r1, 누적 이동 거리, 최대 간선 길이를 0으로 push해준다.
5. v배열의 r1을 true로 변경하여 초기 위치를 방문처리 해준다.
6. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어준다.
7. 변수 cn, cv, mv에 현재 요소의 노드 번호, 누적 이동 거리, 최대 간선 길이를 저장해 준다.
8. 기저 조건으로 만약 현재 노드가 r2라면 cv - mv를 리턴해 준다.
9. 인접리스트를 순회하고, 방문하지 않은 노드라면 방문처리 후 q에 push해준다.
10. bfs함수가 종료된 후 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 서브태스크3을 보고 N이 5000이하라고 인지했는데 100점을 맞기 위해선 N은 100000이 최대값이었다.
2. N을 5001에서 100001로 변경 후 제출하니 AC를 받았다.

 

참고 사항

• 트리 구조이기때문에 두 로봇이 만나지 못할 일은 없다.
• 로봇 하나를 고정해 두고, 하나만 움직여도 된다.
• 로봇이 이동하던 중 가중치가 가장 큰 간선 하나만 빼주면 된다.

 

정답 코드

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

const int N = 100001;
int n, r1, r2;
bool v[N];
struct Edge {
	int nn, nv;
};
vector<Edge> edges[N];
struct Pos {
	int cn, cv, mv;
};

int bfs() {
	queue<Pos> q;
	q.push({ r1, 0, 0 });
	v[r1] = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cn = pos.cn, cv = pos.cv, mv = pos.mv;
		if (cn == r2) return cv - mv;
		//cout << "cn: " << cn << "\n";

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = edge.nv;
			if (v[nn]) continue;
			v[nn] = true;
			q.push({ nn, cv + nv, max(mv, nv)});
		}
	}
	return -1;
}

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

	cin >> n >> r1 >> r2;
	int m = n - 1;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	cout << bfs();
}