BOJ 2479 경로 찾기

사용한 알고리즘

다익스트라, DFS

알고리즘 설명

모든 코드 간에 해밍 거리가 1인 경우 두 코드를 연결하여 연결 그래프를 구성한다.
둘 A와 B사이에 최소의 해밍 거리를 찾기 위해서 A에서 부터 연결 그래프에서 다익스트라 알고리즘을 적용한다.
연결 되지 않은 경우 -1을 출력한다.
DFS를 이용해서 B에서 부터 A까지 다익스트라의 distance조건을 만족하는 코드를 찾아서 스택에 쌓는다.
스택을 뽑으면서 출력하면 A에서 B로 가는 코드 경로가 출력된다.

풀이

// baekjoon 2479 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <stack>
#include <functional>
using namespace std;
const int MAX_N=1001;
const int MAX_K=31;
const int MAX_INF=1e9;
typedef pair<int, int> P;
int N, K, s, t;
char data[MAX_N][MAX_K];
vector<int> adj[MAX_N];
stack<int> st;
bool visited[MAX_N];
int dist[MAX_N];

bool dfs(int here) {
	st.push(here);
	if (here == s) return true;
	bool flag = false;
	for (int i=0; i<adj[here].size(); i++) {
		int nx = adj[here][i];
		if (dist[nx] == dist[here] - 1)
			flag = dfs(nx);
		if (flag) return true;
	}
	return false;
}

int main() {
	scanf("%d%d", &K, &N);
	for (int i=1; i<=K; i++)
		scanf("%s", data[i]);

// 해밍 거리를 찾아 그래프를 구성한다.
	for (int i=1; i<=K; i++) {
		for (int j=i+1; j<=K; j++) {
			int ret = 0;
			for (int k=0; k<N; k++) {
				if (data[i][k] != data[j][k]) ret++;
			}
			if (ret == 1) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}

// 다익스트라 알고리즘을 적용한다.
	fill(dist, dist+MAX_N, MAX_INF);
	priority_queue<P, vector<P>, greater<P> > PQ;
	scanf("%d %d", &s, &t);
	dist[s] = 0;
	PQ.push(P(0, s));
	while (!PQ.empty()) {
		int cur;
		do {
			cur = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[cur]);
		if (visited[cur]) break;
		visited[cur]=true;
		for (int i=0; i<adj[cur].size(); i++) {
			int nx = adj[cur][i];
			if (dist[nx] > dist[cur] + 1) {
				dist[nx] = dist[cur] + 1;
				PQ.push(P(dist[nx], nx));
			}
		}
	}
	if (dist[t] == MAX_INF) return !printf("-1\n");
// 도착점에서 시작점까지 가는 경로를 찾아 낸다.
	dfs(t);
// 결과를 출력한다.
	while (!st.empty()) {
		printf("%d ", st.top());
		st.pop();
	}
	return 0;
}