2644

백준 2644번

Link: 2644번: 촌수계산

---

문제 설명

역시나 BFS문제.

저번에 풀었던 토마토 문제처럼, 이 문제도 트리 내에서 출발지와 목적지를 설정하여 목적지까지 도달하는데 거치는 트리 레벨을 세면 되는 문제였다.

주의해야할 점은 방향이 없는 그래프 문제였다는 점.

이외에는 다소 평이했던 문제였다…

라고 하기에는 막판에 뻘짓을 좀 했다.

도달할 수 없는 경우 -1로 처리하는 부분에서 살짝 헤맸던 것 빼고는 할만한 문제였다.

---

정답 코드

//
// Created by Keith_Lee on 28/01/2019.
//

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int map[101][101] = {0, };
bool visit[101][101] = {false, };

int n;

int BFS(int start, int end){
    int result = 0;

    queue<int> Queue;
    Queue.push(start);

    while(!Queue.empty()){
        vector<int> available;

        while(!Queue.empty()) {
            available.push_back(Queue.front());
            Queue.pop();
        }

        for(int i=0; i<available.size(); i++) {
            int current = available[i];

            for (int j = 1; j <= n; j++) {
                if (map[current][j] == 1 && !visit[current][j]) {
                    visit[current][j] = true;
                    visit[j][current] = true;
                    Queue.push(j);
                }
            }
        }

        result++;

        for(int i=1; i<=n; i++){
            if(visit[end][i] && visit[i][end]){
                return result;
            }
        }

    }
}

int main(){
    cin >> n;

    int start, end;
    cin >> start >> end;

    int m;
    cin >> m;

    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;

        map[x][y] = 1;
        map[y][x] = 1;
    }

    int result = BFS(start, end);

    bool find = false;
    for(int i=1; i<=n; i++){
        if(visit[end][i] && visit[i][end]){
            find = true;
        }
    }

    if(!find){
        result = -1;
    }

    cout << result << '\n';

    return 0;
}

---