[백준/c++] 2644번: 촌수계산

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

2644번: 촌수계산

 

 

문제 요약

 

나 - 아버지, 아버지 - 할아버지 : 1촌

나 - 할아버지 : 2촌

나 - 아버지 형제 : 3촌

 

주어진 두 사람의 촌수를 계산하라. (두 사람의 친척 관계가 전혀 없으면 -1 출력)

 

 

범위

 

전체 사람 수 n (1 ≤ n ≤ 100)

부모 자식들 간의 관계의 개수 m

 

 

 

---

 

 

처음에는 각 루트에서 구해야 하는 사람 노드로 이동하는 것을 생각했다. 하지만 그렇게 하는 것보다는 어차피 두 사람 노드의 거리가 촌수를 나타내는 것과 같으므로 주어진 두 사람 사이의 경로를 구하는 방식으로 생각을 전환했다.

거리 계산을하는 경우 대부분 BFS로 풀며, 방문 여부와 거리를 나타내는 dis 배열을 통해 출발지점으로부터의 거리를 저장해주었다. (만약 0이라면 방문하지 않은 곳이 된다 → 이곳으로 이동해야 한다. 이미 방문했는데도 답이 나오지 않았다는 것은 갈 필요가 없다는 것이다.)

거리는 1씩 증가하므로 만약 방문하지 않은 곳이라면 출발지점에서 이전 노드까지의 거리에 +1을 해서 거리를 업데이트시킨다. 

만약 모두 방문했음에도(큐가 빈 경우) 답이 나오지 않았다면 가족 구성원이 아니므로 -1을 리턴해준다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, x, y, p1, p2, dis[102] = {0};
vector<int> v[102];

void input(){
    cin >> n >> p1 >> p2 >> m;
    for(int i=0; i<m; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void bfs(int s, int e){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x = q.front(); q.pop();
        if(x==e){
            cout << dis[x] << '\n';
            return;
        }
        
        for(int i=0; i<v[x].size(); i++){ //인접한 노드로 이동
            int y = v[x][i];
            if(dis[y] == 0){ //방문하지 않은 곳
                q.push(y);
                dis[y] = dis[x] + 1;
            }
        }
    }
    
    cout << "-1\n"; //이 안에서 안나오면 가족이 아님
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    bfs(p1, p2);
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!