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

코드

#include <iostream>
#include <vector>

using namespace std;

int n,a,b,m,x,y,visited[103];
vector<int> adj[103];

void dfs(int x, int depth) {
    visited[x] = depth;
    for(int i : adj[x]) {
        if(visited[i] == -1) {
            dfs(i, depth + 1);
        }
    }
    return;
}

// 촌수 -> 깊이
int main() {
    cin >> n; // 전체 인원
    cin >> a >> b; // 촌수 계산할 사람
    cin >> m;
    fill(visited, visited + 103, -1);
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(a,0);
    cout << visited[b] << '\n';
    return 0;
}

풀이

현재 노드에서 자식 노드로 이동할 때의 깊이를 방문배열에 저장하면서 촌수를 계산했다. 촌수는 현재 노드에서 목표 노드까지의 깊이를 의미한다고 생각하고 문제에 접근했다.