4454 : 촌수 계산

이번 블로그 글에서는 "촌수 계산"이라는 문제를 해결하는 코드를 소개하고 설명합니다. 이 문제는 주어진 사람들 간의 촌수를 계산하는 프로그램을 작성하는 것을 목표로 합니다. 코드의 구현은 C 언어로 되어 있으며, 문제와 해결 코드는 따옴표로 구분되어 있습니다.

---

문제 설명

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있습니다. 촌수는 부모와 자식 사이를 1촌으로 정의하고, 이로부터 사람들 간의 촌수를 계산합니다. 예를 들어 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되며, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 됩니다.

입력으로는 사람들의 수, 촌수를 계산해야 하는 두 사람의 번호, 부모 자식들 간의 관계의 개수, 그리고 부모 자식 간의 관계가 주어집니다. 주어진 두 사람의 촌수를 계산하여 출력해야 합니다. 만약 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없는 경우 -1을 출력합니다.

 

문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이런한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다.
첫째 줄에는 전체 사람의 수 n이 주어지고,
둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.
그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.
넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다.
이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.
어떤 경우에는 두 사람같의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이 때에는 -1을 출력해야 한다.
입력 예시   예시 복사
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
출력 예시
3

 

---

문제 해결 코드

#include <stdio.h>

int a, s, k[101][101], l[101], g[101], h[101], q, w, e, r;

void f(int v) {
    h[w] = v;
    w = (w + 1) % 101;
}

int f2() {
    int temp = h[q];
    q = (q + 1) % 101;
    return temp;
}

void f3(int v) {
    int b;
    f(v);
    l[v] = 1;
    while (q != w) {
        b = f2();
        for (int i = 1; i < e + 1; i++) {
            if (l[i] == 0 && k[b][i] == 1) {
                l[i] = 1;
                g[i] = g[b] + 1;
                f(i);
            }
        }
    }
}

void f4() {
    f3(a);
    if (g[s] == 0)
        printf("-1");
    else
        printf("%d", g[s]);
}

int main() {
    int o, p;
    scanf("%d %d %d %d", &e, &a, &s, &r);
    for (int i = 0; i < r; i++) {
        scanf("%d %d", &o, &p);
        k[o][p] = 1;
        k[p][o] = 1;
    }
    f4();
}

---

위 코드는 주어진 입력에 따라 촌수를 계산하는 프로그램을 구현한 것입니다.

 

void f(int v): 큐에 정점을 추가하는 함수입니다. 인자로 받은 v를 큐에 저장하고, w를 업데이트합니다.

int f2(): 큐에서 정점을 제거하고 반환하는 함수입니다. q를 업데이트하고, 큐에서 제거된 값을 반환합니다.

void f3(int v): BFS 알고리즘을 구현하는 함수입니다. 인자로 받은 시작 정점 v를 큐에 추가하고, 해당 정점을 방문한 것으로 표시하는 l[v] = 1을 수행합니다. 그 후, 큐가 비어있을 때까지 다음 작업을 반복합니다:

큐에서 정점을 제거하고 b에 저장합니다.
그래프의 각 정점을 확인하면서, 아직 방문하지 않았고 k[b][i]가 1인 경우, 해당 정점을 방문한 것으로 표시하고(l[i] = 1), 이전 정점까지의 거리에 1을 더한 값을 저장합니다(g[i] = g[b] + 1). 마지막으로, 해당 정점을 큐에 추가합니다(f(i)).
void f4(): BFS 알고리즘을 호출하는 함수입니다. 시작 정점 a를 인자로 f3() 함수를 호출합니다. 이후 목적 정점 s까지의 최단 거리를 확인하고, 거리가 0이면 "-1"을 출력하고, 그렇지 않은 경우에는 최단 거리를 출력합니다(printf("%d", g[s])).

int main(): 프로그램의 시작점입니다. 정점의 개수, 시작 정점, 목적 정점, 간선의 개수를 입력받고, 그래프의 연결 관계를 입력받아 k 배열에 저장합니다. 그 후, f4() 함수를 호출하여 최단 거리를 출력합니다.

---

순서도

실행화면

이렇게하여 "촌수 계산" 문제를 해결하는 방법에 대해 알아보았습니다. 문제를 이해하고 코드를 구현하는 과정에서 재귀 함수와 메모이제이션을 활용하는 방법을 사용했습니다. 문제를 해결하기 위해서는 문제를 이해하고 필요한 알고리즘을 설계하는 것이 중요합니다.