백준 2644번 촌수계산 C++ BFS, 너비 우선 탐색

리뷰

촌수를 구하는 완전 탐색 문제, DFS, BFS, 다익스트라 뭘 써도 괜찮을 듯 하다.

 

 

문제 풀이

1. n, sn, dn, m값을 차례로 입력 받고, 방문 처리 배열을 101 크기, 0으로 초기화 해준다.
2. 정수형 2차 벡터 lst에 노드 정보를 받아와 인접 리스트를 생성해 준다, 단 방향이던 양 방향이던 상관 없을듯?
3. 이후 bfs를 돌려주고 시작 노드에서 종료 노드까지의 거리를 구해주는데, 이때 방문 배열에 이전 값 + 1을 해주는 식으로 촌수를 구해주었다.
4. 큐가 빌때까지 while을 돌다가 목표 노드에 도달했을 경우 현재 노드의 방문 배열 값을 리턴해준다.
5. 만약 while이 종료될 때 까지 만나지 못하고 bfs가 종료된다면 -1을 리턴해 준다.
6. 리턴값을 출력해주면 된다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

int n, sn, dn, m;
int v[101] = { 0, };
vector<vector<int>> lst;

int bfs() {
    queue<int> q;
    q.push({ sn });

    while (!q.empty()) {
        int cn = q.front(); q.pop();
        if (cn == dn) return v[cn];
        for (int nn : lst[cn]) {
            if (!v[nn]) {
                v[nn] = v[cn] + 1;
                q.push(nn);
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> sn >> dn >> m;
    lst.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        lst[a].push_back(b);
        lst[b].push_back(a);
    }
    cout << bfs();
}