백준 2479번 경로 찾기 C++

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

 

1. 자신과 다른 모든 코드들을 비교하면서 해밍 거리가 1인 경우만 경로를 추가한다.

2. 입력받은 a에서 b까지 도달할 때까지 bfs탐색을 한다. 탐색 도중에 parent 배열을 이용해서 지나온 경로를 저장한다.

3. parent 배열을 역으로 추적해서 지나온 경로를 추출해서 출력한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k, a, b;
	cin >> n >> k;
	vector<string> codes(n + 1);
	vector<vector<int>> graph(n + 1, vector<int>());
	vector<bool> found(n + 1, false);
	vector<int> parent(n + 1, -1);
	for (int i = 1; i <= n; i++) {
		cin >> codes[i];
	}
	cin >> a >> b;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			int cnt = 0;
			for (int y = 0; y < k; y++) {
				if (codes[i][y] != codes[j][y]) {
					cnt++;
					if (cnt > 1) break;
				}
			}
			if (cnt > 1) continue;
			graph[i].push_back(j);
		}
	}
	queue<int> q;
	q.push(a);
	parent[a] = a;
	found[a] = true;
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		if (curr == b) {
			break;
		}
		for (auto next : graph[curr]) {
			if (found[next]) continue;
			found[next] = true;
			parent[next] = curr;
			q.push(next);
		}
	}
	if (parent[b] == -1) {
		cout << -1;
	}
	else {
		vector<int> ans;
		int curr = b;
		while (true) {
			ans.push_back(curr);
			curr = parent[curr];
			if (curr == parent[curr]) {
				ans.push_back(curr);
				break;
			}
		}
		for (int i = ans.size() - 1; i >= 0; i--) {
			cout << ans[i] << " ";
		}
	}
};