백준 2644번 촌수계산 [C++]

 

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

2644번: 촌수계산

#문제 간단 정리

dfs 혹은 bfs를 사용하자

#문제 해결 방법

dfs를 사용해서 depth를 반환하도록 해줬다.

근데 만들고 나니     result = min(result, curResult); 로 최소 거리를 확인해 줘야 되서

bfs 로 풀면 더 쉽게 풀거라는 생각이 들었따.

#전체 코드

 

dfs 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

bool check[103];

int dfs(int node, vector<vector<int>>& families, int depth, int target) {
    if (node == target) {
        return depth;
    }
    check[node] = true;

    int result = INT_MAX;
    for (int i = 0; i < families[node].size(); i++) {
        int next = families[node][i];
        if (!check[next]) {
            int curResult = dfs(next, families, depth + 1, target);
            if (curResult != -1) {
                result = min(result, curResult);
            }
        }
    }

    return result == INT_MAX ? -1 : result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    int start, target;
    cin >> start >> target;

    vector<vector<int>> families(N + 1);

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

        families[x].push_back(y);
        families[y].push_back(x);
    }

    fill_n(check, 103, false);
    int result = dfs(start, families, 0, target); 

    cout << result << '\n';

    return 0;
}

 

bfs 코드

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

int bfs(int start, int target, vector<vector<int>>& families) {
    vector<bool> visited(families.size(), false);
    queue<pair<int, int>> q; // {노드 번호, 촌수}

    q.push({start, 0}); // 시작 노드와 촌수 0부터 시작
    visited[start] = true;

    while (!q.empty()) {
        int current = q.front().first;
        int distance = q.front().second;
        q.pop();

        if (current == target) {
            return distance;
        }

        for (int next : families[current]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push({next, distance + 1});
            }
        }
    }

    return -1; // 목표 노드에 도달할 수 없는 경우
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    int start, target;
    cin >> start >> target;

    vector<vector<int>> families(N+1);

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

        families[x].push_back(y);
        families[y].push_back(x);
    }

    int result = bfs(start, target, families);

    cout << result << '\n';

    return 0;
}