(c++) DFS 2644번: 촌수계산

https://www.acmicpc.net/problem/2644

 

 

 

문제 개요

 

dfs(깊이 우선 탐색) 응용 문제

 

내 방식대로 풀었기에 다른 사람과 약간 다를 수 있다.

 

부모가 하나로 고정되어있는 트리 형태의 문제로, 주어진 두 사람에 대해서 촌수를 계산하면 된다.

 

아이디어는 아래와 같다.

 

 기존 트리 구조처럼 위에서 아래로 내려오는 구조로 만들게 되면 입력에서 주어진 사람들 찾는데 어려움이 있다.

그래서 반대로 자식을 트리의 윗부분으로 오게 하고, 아랫 부분에 부모 하나를 넣어두었다.

 

첫 번째 사람에 대해서 루트 노드까지 각 촌수를 저장하여 올라간다.

여기서 부모 노드 중 두 번째 사람이 있다면 멈추고 정답을 출력한다.

 

두 번째 사람에 대해서 부모 노드로 올라가면서 똑같이 촌수를 저장하되,

촌수가 이미 기록된 부분을 만나게 되면 가장 가까운 선이 연결되고

 

이미 기록된 촌수 + 두 번째 사람이 기록한 촌수 = 정답 

 

두 번째 사람에 대해서도 부모 노드 중 첫 번째 사람이 있다면 멈추고 정답을 출력한다.

 

예시를 든다면

예제 입력 1에서

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

 

첫 번째 사람 7에 대해서 촌수를 기록 7(0) → 2(1) → 1(2)

두 번째 사람 3에 대해서 촌수를 기록 3(0) → 1(2+1) 

노드 1은 이미 첫 번째 사람에서 2라는 차수를 기록했기에 두 번째 사람이 계산한 촌수 1에 더했다. 

 

추가로 코드 상에서도 메모리를 최대한 덜 쓰는 방법을 도입할 수 있을 것이다.

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int visited[100];
vector<int> graph[100];
int result = 0;

int dfs(int start, int parent, int other) {
    visited[start] = parent;
    int p = 0;
    if (graph[start].size() < 1) {
        return 0;
    } else {
        p = graph[start][0];
        parent++;

        if (p != other && visited[p] == 0) {
            dfs(p, parent, other);
        } else if (p == other){
            result = parent;
        } else if (visited[p] != 0) {
            result = visited[p] + parent;
        }
    }
    return result;
}
int main(void) {
    int n, m;
    cin >> n; // 사람 수

    fill_n(visited, 100, 0); // 배열 초기화

    // 계산 대상 번호 둘
    int person_1, person_2;
    cin >> person_1 >> person_2;

    cin >> m; // 관계 수
    for (int i = 0; i < m; i++) {
        int x, y = 0;
        scanf("%d %d", &x, &y);
        graph[y].push_back(x); // 자식 -> 부모
    }
    int result_1 = dfs(person_1, 0, person_2);
    if (result_1 == 0) { // 첫 번째에서 루트까지 갔다면
        int result_2 = dfs(person_2, 0, person_1);
        if (result_2 != 0) {
            cout << result_2 << endl;
        } else { // 둘다 0인 경우는 다른 트리일 경우로 -1
            cout << "-1" << endl;
        }
    } else { // 첫 번째의 상위 노드 중 두 번째 사람이 있다면
        cout << result_1 << endl;
    }

    return 0;
}