[백준] 2479 - 경로 찾기

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

2479번: 경로 찾기

 

입력으로 1000개의 정점이 주어지고, 또 다른 입력으로 주어지는 A와 B사이의 해밍 경로를 출력하는 것이다.

여기서 해밍 경로라는 것은, 노드를 잇는 모든 해밍 거리가 1인 경로를 뜻한다.

 

입력으로 1000개의 정점이 주어지므로, 모든 정점들의 사이의 해밍 거리를 구할 수 있고,

두 정점 사이의 해밍 거리가 1일 때 인접 리스트에 간선을 추가할 수 있다.

 

이후 bfs를 돌려서 가장 짧은 거리를 구하면 되는데, 여기서 queue자료구조를

queue<pair<int, string>> q;

이런 식으로 정의했다.

string은 바로 실제 거쳐가는 노드의 경로를 저장하기 위해 사용했다.

 

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

int n, m, s, e, vis[1001];
string inp[1001];

// 해밍 거리를 구하는 함수
int getDis(string s1, string s2) {
    int res = 0;
    for (int i = 0; i < m; i++) {
        res += (s1[i] != s2[i] ? 1 : 0);
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> inp[i];
    }
    cin >> s >> e;
    vector<vector<pair<int, int>>> v(n + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) { // 모든 정점을 탐색해서

            int d = getDis(inp[i], inp[j]);

            // 해밍 거리가 1일때만 인접 리스트에 추가
            if (d == 1) {
                v[i].push_back({j, d});
                v[j].push_back({i, d});
            }
        }
    }

    queue<pair<int, string>> q;
    q.push({s, to_string(s)});
    vis[s] = 1;

    // bfs
    while (!q.empty()) {
        int node = q.front().first;
        string path = q.front().second;
        q.pop();

        if (node == e) {
            cout << path;
            return 0;
        }

        for (auto &i : v[node]) {
            if (!vis[i.first]) {
                vis[i.first] = vis[node] + 1;
                q.push({i.first, path + " " + to_string(i.first)});
            }
        }
    }

    cout << -1;
}