백준 2644 - 촌수계산 (c++)

백준 2644 - 촌수계산

문제 링크

생각 및 접근

• 구구절절 말이 길지만, 결국 사람과 사람이 주어질 때, 몇 다리 건너서 만날 수 있는지 구하는 문제였다.
• m[101][101] : 사람들의 촌수 계산을 위해 인접행렬을 선언했다.
• tar1과 tar2가 몇 다리 건너서 만날 수 있는 지 DFS로 풀어보고자 헀다. DFS는 가장 먼저 찾은 해답이 최단 다리라고 보장하지 못하므로, 사실상 모든 경로를 탐색해야 한다. 그나마 탐색하는 경로를 줄이기 위해, 탐색 여부를 저장하는 visit[101]를 선언한다.
• DFS의 종료 조건
  • 내가 탐색하려는 index가 tar2일 때
  • 최단 거리를 저장하는 answer와 cnt를 비교해서 더 작은 값으로 answer를 업데이트한다.
• DFS 탐색

    // 사람 수 만큼 탐색
    for (int i = 1; i <= n; i++) {
        // 아직 탐색되지 않은 사람이고, 연결이 되어 있다면 dfs할 수 있다.
        if (visit[i] == 0 && m[index][i] == 1) {
            visit[i] = 1;
            dfs(i, cnt + 1);
            visit[i] = 0;
        }
    }

코드

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

int m[101][101], visit[101];
int n, a, b, cases, tar1, tar2, answer = 101;

void dfs(int index, int cnt) {
    if (index == tar2) {
        answer = min(answer, cnt);
    }
    else {
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 0 && m[index][i] == 1) {
                visit[i] = 1;
                dfs(i, cnt + 1);
                visit[i] = 0;
            }
        }
    }
}

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

    cin >> n >> tar1 >> tar2 >> cases;
    for (int i = 1; i <= cases; i++) {
        cin >> a >> b;
        m[a][b] = 1;
        m[b][a] = 1;
    }

    visit[tar1] = 1;
    dfs(tar1, 0);

    if (answer == 101)  cout << -1;
    else                cout << answer;
}

채점 결과