[G3] 백준 22868번 산책 (small) C++ 너비 우선 탐색, 정렬

리뷰

 

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

유니크한 노드를 방문하여 시작 노드에서 목표 노드까지 왕복하는 길이를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• edges : 모든 노드의 인접 리스트를 저장할 벡터 배열
• v : 노드 방문 여부를 저장할 배열
• Pos : 현재 노드와 누적 시간을 정의할 구조체

 

함수

1. bfs

int bfs(int f, int t) {
	queue<Pos> q;
	q.push({f, 0});
	v[f] = true;
	int dist = 0;
	vector<int> path(n + 1, 0);

	while (!q.empty()) {
		auto [cn, ct] = q.front(); q.pop();
		if (cn == t) break;

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			path[nn] = cn;
			q.push({ nn, ct + 1 });
		}
	}

	memset(v, false, sizeof(v));
	int cn = t;
	while (cn != f) {
		++dist;
		cn = path[cn];
		v[cn] = true;
	}

	return dist;
}

 

노드 f에서 t까지 가는 거리와 방문한 노드를 방문처리하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 edges를 초기화한다.
2. 1~n번노드를 순회하며 간선의 노드 정보를 오름차순으로 정렬한다.
3. 변수 f, t를 초기화 하고, 시작 노드와 목표 노드를 입력 받아 저장한다.
4. 변수 dist의 값을 bfs함수에 f, t를 매개변수로 전달하여 반환받은 값으로 초기화한다.
5. v[f]를 방문 해제하여 시작 노드에 방문할 수 있게끔 변경한다.
6. dist에 bfs함수에 t, f를 매개변수로 전달하여 반환받은 값을 더해준다.
7. dist에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 정점 E에서 S로 올 때는 S에서 E로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동해야한다.
2. bfs내부에서 별도의 벡터인 path를 통해 이동한 경로를 기억하고, 이동한 노드에 방문 처리를 해주었다.
3. 정점 S에서 정점 E로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다.
4. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

 

정답 코드

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

const int N = 1e4 + 1;
int n, m;
vector<int> edges[N];
bool v[N];
struct Pos {
	int cn, t;
};

int bfs(int f, int t) {
	queue<Pos> q;
	q.push({f, 0});
	v[f] = true;
	int dist = 0;
	vector<int> path(n + 1, 0);

	while (!q.empty()) {
		auto [cn, ct] = q.front(); q.pop();
		if (cn == t) break;

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			path[nn] = cn;
			q.push({ nn, ct + 1 });
		}
	}

	memset(v, false, sizeof(v));
	int cn = t;
	while (cn != f) {
		++dist;
		cn = path[cn];
		v[cn] = true;
	}

	return dist;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	while (m--) {
		int f, t; cin >> f >> t;
		edges[f].push_back(t);
		edges[t].push_back(f);
	}

	for (int i = 1; i <= n; ++i) {
		sort(edges[i].begin(), edges[i].end());
	}

	int f, t; cin >> f >> t;
	int dist = bfs(f, t);
	v[f] = false;
	dist += bfs(t, f);
	cout << dist;
}