백준2479 - 경로 찾기

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

2479번: 경로 찾기

map을 이용하여 bfs로 푼 문제이다.

 

map을 사용하는 이유는 이진코드를 순서대로 번호를 부여하여 관리하기 위함이다. 문자열을 입력을 받아서 모두 서로 비교를 하여 딱 한자리만 다른 경우 인접 행렬로 표시한다. 인접 행렬로 표시할 때는 map으로 구한 결과를 이용하였다.

 

그런 후 bfs를 이용하여 현재 위치, 경로를 저장한 후 원하는 위치까지 갈 수 있는 경우는 경로를 출력하고 그렇지 못한 경우는 -1을 출력하였다.

 

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

int N, K, A, B;
map<string, int> mp;
vector<string> v;
vector<int> moving[1001];
bool visit[1001] = {false,};
string s, ans;
bool check = false;

void bfs(int start, int stop) {
    queue<pair<int, string>> q;
    q.push(pair<int, string>(start, to_string(start)));
    visit[start] = true;
    
    while(!q.empty()) {
        int x = q.front().first;
        string str = q.front().second;
        q.pop();
        
        if(x == stop) {
            check = true;
            ans = str;
            return;
        }
        
        for(int i = 0; i < moving[x].size(); i++) {
            if(!visit[moving[x][i]]) {
                visit[moving[x][i]] = true;
                q.push(pair<int, string>(moving[x][i], str + ' ' + to_string(moving[x][i])));
            }
        }
    }
}

int main() {
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        cin >> s;
        v.push_back(s);
        mp[s] = i;
    }
    cin >> A >> B;
    
    for(int i = 0; i < v.size(); i++) {
        for(int j = i + 1; j < v.size(); j++) {
            int cnt = 0;
            for(int x = 0; x < K; x++) {
                if(cnt >= 2) {
                    break;
                }
                if(v[i][x] != v[j][x]) {
                    cnt++;
                }
            }
            if(cnt == 1) {
                moving[mp[v[i]]].push_back(mp[v[j]]);
                moving[mp[v[j]]].push_back(mp[v[i]]);
            }
        }
    }
    
    bfs(A, B);
    
    if(check) {
        cout << ans;
    }
    else {
        cout << -1;
    }
}