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

문제

[C++] 백준 2644: 촌수계산 SILVER 2
https://www.acmicpc.net/problem/2644

 

---

 

접근 방법

이 문제는 사람 사이의 촌수(거리) 를 구하는 문제로,
가족 관계를 그래프로 표현한 뒤 두 정점 사이의 거리를 탐색하면 된다.

• 사람 → 정점(Node)
• 부모–자식 관계 → 간선(Edge)

결국 시작 노드(s)에서 목표 노드(e)까지의 최단 거리를 구하는 문제이므로 DFS 또는 BFS를 사용할 수 있으며,
이번 풀이에서는 DFS를 이용하였다.

가장 중요했던 점은 가족 관계가 방향 그래프가 아니라 무방향 그래프라는 것이다.
처음에는 부모 → 자식 방향으로만 생각했지만, 촌수는 위아래 개념이 아니라 사람 사이의 거리 개념이기 때문에 부모와 자식은 서로 오갈 수 있어야 한다.

DFS 탐색 시에는 다음 노드로 이동할 때마다 촌수(cnt)를 1씩 증가시키며,
목표 노드를 찾았을 때의 cnt 값이 곧 두 사람 사이의 촌수가 된다.

 

구현 시 주의할 점

DFS는 여러 경로를 탐색하기 때문에 촌수 변수의 관리가 매우 중요하다.

 

재귀 호출 전에 cnt를 증가시키고, 호출이 끝난 뒤에는 반드시 cnt를 감소시켜 이전 상태로 되돌려야 한다.
이 과정을 하지 않으면 촌수가 누적되어 잘못된 결과가 나오게 된다.

 

또한 visited 배열을 사용해 이미 방문한 사람을 다시 방문하지 않도록 하여 불필요한 탐색을 방지했다.

 

---

 

코드

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

int n, s, e, m;
vector<vector<int>> graph;
vector<bool> visited;
int cnt;
bool flag;

void dfs(int node)
{
    if (node == e)
    {
        cout << cnt;
        flag = true;
        return;
    }

    visited[node] = true;

    for (int i = 0; i < graph[node].size(); i++)
    {    
        if (visited[graph[node][i]] == true)
            continue;

        cnt++;
        dfs(graph[node][i]);
        cnt--;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> s >> e >> m;

    graph.resize(n + 1, vector<int>(0));
    visited.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int x = 0, y = 0;
        cin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(s);

    if (!flag)
        cout << -1;

    return 0;
}