#2644 촌수계산 (C++)

링크 : www.acmicpc.net/problem/2644

2644번: 촌수계산

 

문제 풀이는 다음과 같다.

 

(1) 사람의 숫자가 1번부터 100번까지 주어질 수 있으므로, 배열의 크기는 101번까지 지정해준다.

(vector로 풀어도 무방하다)

(2) 1번과 3번이 부모자식 관계라면, 배열의 [1][3], [3][1]모두 값을 증가시켜준다. 

두 가지를 모두 증가시켜야 하는 이유는 n에서 DFS를 시작하건 m에서 DFS를 시작하건 무방하게 답을 구하기 위함이다. 

(3) n이나 m중 한 곳에서 DFS를 진행한다.

(4) 방문되지 않은 사람이라면 true로 bool문을 선정하고, 해당 사람과 부모 혹은 자식 관계인 노드들을 for문으로 찾는다. 

(5) 관계성이 있는 노드가 false라면 DFS를 진행하고, 이때 촌수의 값 y를 증가시킨다. 

(6) 촌수값을 찾고자하던 노드가 DFS의 대상이 될 경우, 촌수의 값 y를 출력하고 종료시킨다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0, n = 0, m = 0, t = 0, arr[101][101];
bool check[101];

void dfs(int x, int y) {
    if (x == m) {
        cout << y << "\n";
        exit(0);
    }
    if (check[x] == false) {
        check[x] = true;
        for (int i = 0; i < 101; i++) {
            if (arr[x][i] > 0) {
                dfs(i,y+1);
            }
        }
    }
    return;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = 0, b = 0;
    cin >> cnt;
    cin >> n >> m;
    cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> a >> b;
        arr[a][b]++;
        arr[b][a]++;
    }

    dfs(n,0);
    cout << -1 << "\n";
    return 0;
}

졸면서 풀다가 exit(0)이 아닌 exit(1)로 적어서 에러가 나버렸다.