(매일 BOJ) C++ 2644번 촌수계산

이번 문제는 2644번 촌수계산이다.

문제 요약

• 사람 수 n
• 두 사람 start, end가 주어지고, 이 둘 사이의 촌수를 구하기
• 이어서 m개의 관계 정보가 (a, b) 형태로 주어짐. 이는 a와 b가 서로 가족 관계라는 의미
• 관계는 양방향

접근 방식

문제를 그래프로 생각하면 단순해진다. 사람은 정점(Node), 가족 관계는 간선(Edge)
DFS를 이용해 start에서 출발해 end까지 탐색하고, 몇 단계(간선)를 거쳤는지를 세어주면 된다

주의할 점

DFS에서는 재귀 호출을 통해 깊이를 누적하는데, 정답을 못 찾고 돌아오는 경우에는 깊이를 되돌려야 한다
이걸 백트래킹(backtracking)이라고 하며, 이번 문제의 핵심이다.

 

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS(int* start, int* end, int* count, int* result, vector<bool>& visited, vector<int>* v) {
    visited[*start] = true;

    for (int i : v[*start]) {
        if (!visited[i]) {
            (*count)++;
            if (i == *end) {
                *result = *count;
                return;
            }
            DFS(&i, end, count, result, visited, v);
            if (*result != -1) return;
            (*count)--;  // 백트래킹
        }
    }
}

int main(void) {
    int n;
    cin >> n;

    int start, end;
    cin >> start >> end;

    int m;
    cin >> m;
    vector<int> v[n + 1];

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for (int j = 1; j <= m; j++) {
        sort(v[j].begin(), v[j].end()); // 정렬은 필수는 아님
    }

    vector<bool> visited(n + 1);
    int result = -1;
    int count = 0;

    DFS(&start, &end, &count, &result, visited, v);

    cout << result;
}

코드 설명

• vector<int> v[n + 1]: 각 사람마다 연결된 가족 리스트를 저장.
• visited[]: 방문 여부 확인용
• DFS(): 깊이 우선 탐색 함수로, 재귀적으로 관계를 따라가며 count를 증가.
• *result = *count: 목표 사람에 도달하면 현재 촌수를 저장
• (*count)--: 탐색 후에는 이전 깊이로 되돌림 (백트래킹).