99클럽 코테 스터디 8일차 TIL + DFS(C++)

문제

[백준]2644번: 촌수계산

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

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> visited(101);
vector<int> graph[101];

void dfs(int x) {
    for (int y : graph[x]) {
        if (!visited[y]) {
            visited[y] = visited[x] + 1;
            dfs(y);
        }
    }
}

int main() {
    int n;
    int a, b;
    int m;

    cin >> n;
    cin >> a >> b;
    cin >> m;

    while (m--) {
        int x, y;
        cin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(a);

    cout << (visited[b] == 0 ? -1 : visited[b]);

    return 0;
}

 

풀이

촌수는 두 사람 간의 관계를 나타내는 ‘거리’, 즉 ‘단계 수’를 찾는 개념이다.

결론부터 말하면 촌수는 DFS(또는 BFS) 알고리즘을 사용해 계산할 수 있다. (이 풀이에서는 DFS를 사용했다.)

이해를 위해 그림을 통해 알아가보자.

우선, 주어진 예제1과 같이 각 사람들간의 부모 자식 관계가 주어졌을 때, 이를 바탕으로 다음과 같은 가족관계도를 그릴 수 있다.

 

 

위 관계도에서 각각의 사람을 하나의 노드로 생각하여 인접 리스트로 표현하면 다음과 같다.

1: [2, 3]
2: [1, 7, 8, 9]
3: [1]
4: [5, 6]
5: [4]
6: [4]
7: [2]
8: [2]
9: [2]

 

이렇게 노드들이 서로 연결되어 인접 리스트를 구성하고 있을 때,

주어진 두 노드(예제 1의 경우 7번과 3번) 중 하나를 시작 노드로 설정하고 DFS를 실행하면 두 노드간의 촌수를 계산할 수 있다.

이때, DFS에서 재귀호출시 촌수가 증가되는 공식은 다음의 3가지 촌수계산의 기본원리를 따른다.

• 나와 나 자신의 관계는 0촌
• 내 자식은 나보다 +1촌
• 형제끼리의 촌수는 같음

위 공식을 바탕으로 7번부터 DFS를 실행하는 과정을 떠올려보면 3번과의 촌수가 3임을 도출해낼 수 있을 것이다.

 

이 공식을 DFS 코드로 표현하면 다음과 같다.

void dfs(int x) {
    for (int y : graph[x]) {
        if (!visited[y]) {
            visited[y] = visited[x] + 1; // 내 자식은 나보다 +1촌 & 형제끼리는 촌수같음
            dfs(y);
        }
    }
}

 

(visited[n]에는 시작 노드인 a번과 n번 노드의 촌수가 저장된다.)

 

이렇게 시작 노드에서부터 연결된 노드를 방문하며 탐색을 진행하고, 각 방문 경로마다 촌수를 하나씩 추가해나가는 과정을 통해 시작 노드로부터 목표 노드까지의 거리, 즉 촌수를 구할 수 있다.

 

회고

이 문제는 아무래도 촌수에 대한 지식이 어느정도는 바탕이 된 상태로 풀어야하는 것 같다.

나는 이전에 촌수계산법을 잘 몰랐어서(…) 구글링으로 촌수에 대한 개념을 어느정도 익힌 후에 풀기 시작했다.

하지만 DFS 알고리즘을 사용하면 되겠다는 걸 깨닫고 나서도 촌수를 증가시키는 로직을 어떻게 구현해야할지 제대로 감이 안 왔는데, 촌수계산의 기본원리를 정리하고 나니 자연스럽게 정답이 떠올랐다! 역시 공식을 항상 일반화해보는 작업이 중요한 것 같다.