촌수계산

작성일 | In

[백준] 2644번 - 촌수계산

문제 링크

부모 자식 관계인 여러 개의 정수쌍을 입력받아 이를 그래프화하고, dfs로 탐색하여 풀었다.
기본적인 dfs 풀이법을 사용하면 정답을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<bool> visited;

int dfs(int cur, int target, int cnt) {
    if(cur == target)
        return cnt;
    
    for(int i=0; i<adj[cur].size(); ++i) {
        int next = adj[cur][i];
        if(visited[next])
            continue;
        
        visited[next] = true;
        int res = dfs(next, target, cnt+1);
        visited[next] = false;

        if(res != -1)
            return res;
    }

    return -1;
}

int main(void) {
    int n, m;
    int tc, tp;
    scanf("%d", &n);
    scanf("%d %d", &tc, &tp);

    adj.resize(n+1);
    scanf("%d", &m);
    for(int i=0; i<m; ++i) {
        int x,y;
        scanf("%d %d", &x, &y);
        adj[y].push_back(x);
        adj[x].push_back(y);
    }

    visited.resize(n+1, false);
    visited[tc] = true;
    printf("%d", dfs(tc, tp, 0));
}
0%