백준 2644번 촌수계산 C++ 풀이

백준 2644번 촌수계산 C++ 풀이

문제

가족 혹은 친척들 사이의 관계를 나타내는 촌수를 계산하는 프로그램을 작성합니다.
촌수는 부모와 자식 사이를 1촌으로 정의하고, 이로부터 몇 단계를 거쳐야 하는지를 계산합니다.
예를 들어, 나와 아버지는 1촌이고, 나와 할아버지는 아버지를 거쳐 가므로 2촌입니다.
아버지의 형제(삼촌)는 아버지와 형제이므로 할아버지를 기준으로 보면 둘 다 1촌이고, 나와 삼촌은 할아버지를 거쳐야 하므로 3촌입니다.

입력으로는 사람의 수, 촌수를 계산해야 하는 두 사람의 번호, 그리고 부모 자식 관계들이 주어집니다.
이때, 두 사람의 촌수를 출력하고, 만약 친척 관계가 없다면 -1을 출력합니다.

테스트케이스

입력 예시 1

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

출력 예시 1

3

입력 예시 2

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

출력 예시 2

-1

문제 설명

이 문제에서는 사람마다 번호가 붙어 있고, 부모-자식 관계가 표로 주어집니다.
이 표를 바탕으로 서로 몇 단계만에 만날 수 있는지를 계산하는 것입니다.
예를 들어 첫 번째 예제에서는 다음과 같은 관계가 있습니다.

1
├── 2
│   ├── 7
│   ├── 8
│   └── 9
└── 3

여기서 7번과 3번의 촌수를 구합니다.
7번에서 위로 올라가면 2번(1촌), 1번(2촌)이고, 1번에서 3번으로 내려가면 3촌입니다.
즉, 7번과 3번 사이에는 3촌의 거리가 존재합니다.

두 번째 예제에서는 8번과 6번 사이의 촌수를 구합니다.
8번은 2번의 자식이고, 6번은 4번의 자식인데, 2번과 4번 사이에 연결된 관계가 없으므로 친척이 아니고 -1을 출력합니다.

다르게 표현하면, 서로 다른 사람을 정점(노드)으로 생각하고 부모-자식 관계를 간선(연결선)으로 두었을 때, 두 정점 사이의 최단 거리를 계산하는 문제입니다.
이때 부모와 자식 모두 서로 왕래할 수 있기 때문에 양방향으로 탐색하면 됩니다.

아이디어

이 문제는 가족 관계를 통해 두 사람이 몇 촌인지 계산하는 문제입니다.
촌수란 두 사람 사이를 부모-자식 관계를 따라 몇 단계 이동해야 하는지를 뜻합니다.
예를 들어, 다음과 같은 가족이 있다고 가정합니다.

      1
     / \
    2   3
   / \
  4   5

여기서 4번과 3번의 촌수를 계산합니다.
4번 → 2번(1촌), 2번 → 1번(2촌), 1번 → 3번(3촌)으로 총 3촌입니다.

이처럼 사람들을 노드(점)로, 부모-자식 관계를 간선(선)으로 생각하면 하나의 그래프가 됩니다.
그래프 탐색을 통해 두 노드 사이의 “최단 거리”를 계산하면 촌수가 됩니다.
여기서 최단 거리를 찾기 위해 적합한 탐색법은 BFS(너비 우선 탐색)입니다.

BFS의 정의

BFS(너비 우선 탐색)는 탐색 알고리즘의 하나로, 현재 지점에서부터 가까운 곳을 모두 탐색한 후에 더 먼 곳을 탐색하는 방식입니다.
즉, 현재 단계에서 갈 수 있는 모든 사람을 먼저 탐색하고, 그다음 단계로 넘어갑니다.
이 때문에 탐색이 진행될수록 거리(단계)가 하나씩 늘어나며, 가장 처음 목표에 도달했을 때의 거리가 바로 최단 거리입니다.

DFS(깊이 우선 탐색)는 한 방향으로 끝까지 가서 답을 찾는 방식이라서 더 긴 경로를 찾을 수도 있습니다.
이 문제에서는 두 사람 사이의 최소 촌수를 구해야 하므로, BFS가 적합합니다.

BFS의 적절성

앞서 본 예시 그래프에서 5번과 3번의 촌수를 계산한다고 가정합니다.

      1
     / \
    2   3
   / \
  4   5

5번에서 출발하면 이렇게 단계별로 탐색이 진행됩니다:

• 첫 번째 단계: 5번 → 부모인 2번(1촌)
• 두 번째 단계: 2번 → 부모인 1번(2촌)과 다른 자식인 4번(2촌)
• 세 번째 단계: 1번 → 자식인 3번(3촌)

이처럼 BFS는 가까운 사람부터 순서대로 탐색하기 때문에, 가장 빠른 순간에 목표에 도달할 수 있습니다.

BFS의 동작 과정

아래는 BFS 탐색이 실제로 어떻게 진행되는지를, 그래프 다이어그램과 함께 단계별로 설명한 것입니다.
각 단계마다 현재 탐색 중인 사람(노드)에는 [ ]로 표시하고, 그 단계에서 새롭게 탐색되는 사람들은 아래 설명에 간선 방향으로 나타냅니다.
큐 상태도 함께 기록해 현재 어떤 사람들을 기다리고 있는지 알려줍니다.

0단계: 탐색 시작

      1
     / \
    2   3
   / \
  4  [5] 

• 지금은 5번에서 시작합니다.
• 5번은 자기 부모인 2번과 연결돼 있습니다.
• 5번을 탐색하면서 2번을 큐에 넣습니다.

현재 탐색: [5] → [2]
큐 상태: [2]
방문 표시: [5, 2]

1단계: 2번 탐색

      1
     / \
   [2]  3
   / \
  4   5

• 이번에는 큐에서 2번을 꺼내 탐색합니다.
• 2번의 부모인 1번, 다른 자식인 4번을 찾아 큐에 넣습니다.
• 이렇게 하면 2촌 거리의 사람들을 모두 탐색할 준비가 됩니다.

현재 탐색: [2] → [1, 4]
큐 상태: [1, 4]
방문 표시: [5, 2, 1, 4]

2단계: 1번 탐색

     [1]
     / \
    2   3
   / \
  4   5

• 이번에는 큐에서 1번을 꺼내 탐색합니다.
• 1번의 다른 자식인 3번을 찾아 큐에 넣습니다.
• 이때 3번을 발견했기 때문에 다음 단계에서 목표에 도달하게 됩니다.

현재 탐색: [1] → [3]
큐 상태: [4, 3]
방문 표시: [5, 2, 1, 4, 3]

3단계: 3번 탐색

      1
     / \
    2  [3]
   / \
  4   5

• 마지막으로 큐에서 3번을 꺼내 탐색합니다.
• 3번이 바로 우리가 찾던 사람입니다.
• 현재 단계는 3촌입니다. BFS 탐색을 여기서 종료합니다.

현재 탐색: [3] → 목표 도달
큐 상태: [4] (남았지만 탐색 종료)
최종 촌수: 3

전체 코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int main(void)
{
    int N,a,b,m,x,y;
    int arr[101][101]={0,};
    int dis[101]={0},check[101]={0};
    cin>>N;
    cin>>x>>y;
    cin>>m;
    
    queue<int> q;
    
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        arr[a][b]=1;
        arr[b][a]=1;
    }
    
    q.push(x);
    check[x]=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=1;i<=N;i++)
        {
            if(i==x)
                continue;
            if(arr[x][i]==1 && check[i]==0)
            {
                dis[i]=dis[x]+1;
                check[i]=1;
                q.push(i);
            }
        }
    }
    
    if(dis[y]==0)
        cout<<-1<<endl;
    else
        cout<<dis[y]<<endl;
   
    return 0;
}

개별 코드 설명

입력 처리

cin>>N;
cin>>x>>y;
cin>>m;

• N : 전체 사람 수를 입력받습니다.
• x, y : 촌수를 계산해야 하는 두 사람의 번호입니다.
• m : 부모-자식 관계의 수입니다.

즉, 문제에서 주어진 기본 정보를 입력받아 변수에 저장하는 부분입니다.

부모-자식 관계 입력 및 관계 저장

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

• m번 반복하면서 두 사람 a, b의 부모-자식 관계를 입력받습니다.
• arr[a][b]=1, arr[b][a]=1 : 두 사람이 서로 연결돼 있음을 기록합니다.
  (양방향으로 탐색해야 하기 때문에 두 방향 모두 1로 설정합니다.)

이 배열은 두 사람 간의 연결 여부를 쉽게 확인하기 위해 사용합니다.

BFS 탐색 준비

q.push(x);
check[x]=1;

• x를 큐에 넣어 BFS 탐색을 시작합니다.
• check[x]=1로 방문 표시를 합니다.

이제 x부터 가까운 사람들을 차례로 탐색합니다.

BFS 탐색 실행

while(!q.empty())
{
    x=q.front();
    q.pop();

• 큐가 빌 때까지 탐색을 반복합니다.
• 현재 탐색할 사람 x를 큐에서 꺼냅니다.

현재 사람과 연결된 사람 확인

for(int i=1;i<=N;i++)
{
    if(i==x)
        continue;
    if(arr[x][i]==1 && check[i]==0)
    {
        dis[i]=dis[x]+1;
        check[i]=1;
        q.push(i);
    }
}

• 현재 사람 x와 연결된 사람들을 모두 확인합니다.
• 아직 방문하지 않았고(check[i]==0), 연결돼 있다면(arr[x][i]==1):
• dis[i]=dis[x]+1 : x의 거리보다 1 더해 기록합니다.
• check[i]=1 : 방문 표시
• q.push(i) : 큐에 추가해 다음 탐색 대상으로 등록합니다.

이 과정으로 가까운 사람부터 촌수를 차례로 계산할 수 있습니다.

최종 결과 출력

if(dis[y]==0)
    cout<<-1<<endl;
else
    cout<<dis[y]<<endl;

• 탐색이 끝난 후 y의 dis[y]가 0이면 두 사람은 연결되지 않았다는 뜻 → -1 출력
• 그렇지 않으면 dis[y]에 기록된 촌수를 출력

결론

• BFS는 가까운 사람부터 탐색하기 때문에, 두 사람 사이의 최단 촌수를 정확히 계산할 수 있습니다.
• 인접 행렬을 사용하면 부모-자식 관계를 빠르게 조회할 수 있어 구현이 간단합니다.
• 방문 배열과 거리 배열을 함께 사용해 탐색의 정확성을 보장하고, 거리(촌수)를 기록합니다.
• 큐를 사용해 탐색 순서를 올바르게 유지해 단계별로 진행할 수 있습니다.