[백준] 2644 촌수계산 c++

 

문제 링크 https://www.acmicpc.net/problem/2644

KEY

• 두 노드 사이의 거리를 구하는 문제이므로, 하나의 노드를 기준으로 다른 노드에 도착할 때까지 거리를 증가시킨다.
• DFS풀이의 경우 재귀함수의 종료조건은 n번 순회를 끝낼 때로 정했다.
• 구하고자 하는 거리 배열을 0으로 초기화했기 때문에 방문하지 않은 노드의 경우 0이 된다.

 

◈ DFS풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int n;
int p1, p2;
int m;
vector<vector<int>> v;
int dist[MAX];
 
void dfs(int node, int cnt) {
    if (cnt == n) //n번 순회시 종료
        return;
    for (int i = 0; i < v[node].size(); i++) {
        int next = v[node][i];
        if (dist[next] == 0) { //방문하지 않은 곳이라면
            dist[next] = dist[node] + 1;
            dfs(next, cnt + 1);
        }
    }
}
int main(void) {
    cin >> n;
    cin >> p1 >> p2;
    cin >> m;
    v.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int parent, child;
        cin >> parent >> child;
        v[parent].push_back(child);
        v[child].push_back(parent);
    }
    dfs(p1, 0);
 
    if (dist[p2] == 0)
        cout << -1;
    else
        cout << dist[p2];
}

 

◈ BFS풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int n;
int p1, p2;
int m;
vector<vector<int>> v;
int dist[MAX];
 
int bfs(int start, int end) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
 
        if (front == end) //종료조건
            return dist[end];
 
        for (int i = 0; i < v[front].size(); i++) {
            int next = v[front][i];
            if (dist[next] == 0) { //방문하지 않은 곳이면
                q.push(next);
                dist[next] = dist[front] + 1;
            }
        }
    }
    return -1;
}
 
int main(void) {
    cin >> n;
    cin >> p1 >> p2;
    cin >> m;
    v.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int parent, child;
        cin >> parent >> child;
        v[parent].push_back(child);
        v[child].push_back(parent);
    }
 
    cout << bfs(p1, p2);
}