[G4] 백준 2479번 경로 찾기 C++ 너비 우선 탐색

리뷰

 

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

비트 차이가 한개 나는 노드끼리 간선을 연결하고 특정 노드에서 목표 노드로 이동 가능한 경로를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 길이를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• l : 노드의 비트 개수를 저장할 변수
• H : 노드의 비트 정보를 저장할 배열
• c : 어떤 노드로 부터 왔는지를 저장할 배열
• v : 방문 여부를 체크할 배열
• edges : 간선 정보를 인접 리스트로 저장할 벡터 배열

 

함수

1. bfs

vector<int> bfs(int sn, int en) {
	queue<int> q;
	q.push(sn);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		if (cn == en) break;

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			c[nn] = cn;
			q.push(nn);
		}
	}

	if (!v[en]) return {};

	vector<int> path(1, en);
	while (en != sn) {
		en = c[en];
		path.push_back(en);
	}
	return path;
}

 

sn에서 en으로 갈 수 있는지를 판단하고, 갈 수 있다면 이동 경로를 반환하기 위한 함수

 

 

문제풀이

1. n, l값을 입력 받고, n개의 노드의 비트 정보를 H배열에 입력 받아준다.
2. 노드간 비트 차이가 정확히 1인 경우에만 인접 리스트 edges에 양방향 간선을 추가해 준다.
3. 변수 sn, en에 시작 노드와 목표 노드의 번호를 입력 받아준다. bfs함수에 sn, en을 전달하여 호출한다.
4. 정수타입 큐 q를 초기화 하고, sn을 push해주고, v배열을 통해 sn에 방문 처리를 진행해 준다.
5. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내 변수 cn에 노드 번호를 저장해 준다.
6. 기저 조건으로 cn이 en과 같을 경우 목표 노드에 도달한 것이므로 break처리해 준다.
7. edges[cn]을 순회하며 다음 노드인 nn이 방문 되어있다면 continue처리해 준다.
8. 방문하지 않은 경우 방문처리 및 c[nn] = cn을 통해 cn으로 부터 nn에 도달했음을 명시하고 nn을 q에 삽입해 준다.
9. while루프가 종료된 후 v[en]이 false인 경우 en에 도달하지 못한 것이므로 빈 벡터를 반환해 준다.
10. v[en]이 true인 경우 정수형 벡터 path를 초기값 en이 들어가 있는 상태로 초기화 해준다.
11. en부터 출발하여 c배열을 이용해 en이 sn에 도달할 때 까지 경로를 역추적 하여 path에 push해준다.
12. 경로 역추적이 완료하였을 경우 path를 반환해 준다.
13. 정수형 벡터 res에 bfs함수의 반환값을 저장하고, res가 비었다면 -1을 출력해 준다.
14. res가 비지 않았을 경우 res배열을 뒤집어준 다음 저장된 요소를 공백을 기준으로 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. N이 최대 1000이므로 브루트포스를 활용해 모든 노드간 비트가 1차이인 해밍 경로만 간선으로 추가해 주었다.
2. 경로 역추적 시 en -> sn으로의 경로가 저장되므로 reverse를 통해 경로를 뒤집어 주어야 한다.

 

정답 코드

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

const int N = 1001;
int n, l;
string H[N];
int c[N];
bool v[N];
vector<int> edges[N];

vector<int> bfs(int sn, int en) {
	queue<int> q;
	q.push(sn);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		if (cn == en) break;

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			c[nn] = cn;
			q.push(nn);
		}
	}

	if (!v[en]) return {};

	vector<int> path(1, en);
	while (en != sn) {
		en = c[en];
		path.push_back(en);
	}
	return path;
}

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

	cin >> n >> l;
	for (int i = 1; i <= n; ++i) cin >> H[i];

	for (int i = 1; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			int cnt = 0;

			//cout << H[i].size() << " " << H[j].size() << "\n";
			for (int k = 0; k < l; ++k) {
				if (H[i][k] != H[j][k]) cnt++;
				if (cnt >= 2) break;
			}

			if (cnt == 1) {
				edges[i].push_back(j);
				edges[j].push_back(i);
			}
		}
	}

	int sn, en; cin >> sn >> en;
	vector<int> res = bfs(sn, en);

	if (res.empty()) cout << -1;
	else {
		reverse(res.begin(), res.end());
		for (int i : res) cout << i << " ";
	}
}