[C++]백준 2644번 - 촌수계산 (BFS)

문제

문제 링크 : www.acmicpc.net/problem/2644

2644번: 촌수계산

 

촌수계산 실패출처분류

문제

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

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

 

 

 

접근 방법  1

해당 노드의 부모 노드의 번호를 parentArr[] 에 저장했다. 단, 루트 노드에 해당하면 0을 저장한다.

while문을 돌면서 루트 노드까지 거슬러 올라가며, 올라갈때마다 sum 값을 1씩 증가시켰다.

그 후 node1 ~ root까지의 합인 sum1과 node2 ~ root까지의 합인 sum2를 더하여 답을 구해보았다.

 

(알고리즘 분류는 DFS이지만 DFS로 풀지 않았다.)

 

아래와 같이 코드를 작성했는데 18%정도에서 '틀렸습니다' 메세지가 나와서 백준 사이트 문제 게시판에 있는 반례들을 입력해보았는데 결과는 모두 올바르게 출력되었다. 뭐가 문제인지 모르겠다.

 

 

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

int n,m;
int node1, node2;
int parent, child;

int parentArr[101] = {0};


vector<int> findParent(int child){
    
    vector<int> vec;
    int sum = 0;
    
    while(1){
            
        int parent = parentArr[child];
        if(parent == 0) {
            
            vec.push_back(child);    //루트노드
            vec.push_back(sum);     //그 루트노드까지 거슬러 올라간 길이(촌수)
            break;
        }                           //거슬러 올라가다 node2를 만나버리면
        else if(child==node2){
            vec.push_back(-1);
            vec.push_back(sum);
            break;
        }
        else{
            sum+=1;
            child = parent;
        }
    }
    return vec;
}



int main(){
    
    int answer = 0;
    
    cin>>n;
    cin>>node1 >> node2;
    cin>>m;

    for(int i = 0; i<m; i++){
        cin >> parent >> child;
        parentArr[child] = parent;
    }

    
    vector<int> ansVec1 = findParent(node1);
    vector<int> ansVec2 = findParent(node2);
    
    if(ansVec1[0]==-1){             //거슬러 올라가다가 만난
        answer = ansVec1[1];
    }
    else{
        if(ansVec1[0]!=ansVec2[0]){
            answer = -1;
        }
        else{
            answer = ansVec1[1] + ansVec2[1];
        }
    }
    

    cout << answer << endl;
  
    return 0;
}

 

 

 

접근 방법 2

BFS로 다시 도전해보았다. 시작 노드에서 시작해서 해당 노드와 연결된 노드들을 조사한다.

 

1) 조사를 진행하면서 연결된 노드가 타겟 노드에 해당하지 않으면 '시작노드에서 해당 노드까지의 거리'를 저장하는 fromStart[] 의 값을 증가시키고 해당 노드를 다시 큐에 넣는다.

2) 연결된 노드가 타겟노드에 해당하면 fromStart[해당노드]의 값을 리턴한다.

 

 

 

vector<int> connected[]

- connected[i]에는 노드i 와 연결된 노드들이 벡터에 담겨 저장되어 있다.

 

 

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


queue<int> que;
int fromStart[101];
vector<int> connected[101];     //연결된 노드들이 벡터에 저장되어 각 배열에 들어있음

int BFS(int start, int end){
    
    while(!que.empty()){
        
        int x = que.front();
        que.pop();
        
        if(x==end){                     //타겟 노드 찾으면 시작노드부터 그 노드까지 거리 리턴
            return fromStart[x];
        }
        
        else{
            for(int i = 0; i<connected[x].size(); i++){
                int next = connected[x][i];
                
                if(fromStart[next]==0){ //아직 방문 안한 곳
                    que.push(next);
                    fromStart[next] = fromStart[x] + 1;
                }
            }
        }
    }
    
    return -1;

}


int main(){
    
    int answer = 0;
    int n,m;
    int node1, node2;
    int parent, child;

    
    cin >> n >> node1 >> node2 >> m;

    
    for(int i = 0; i<m; i++){
        cin >> parent >> child;
        connected[parent].push_back(child);     //양방향 연결
        connected[child].push_back(parent);

    }
    
    que.push(node1);
    
    answer = BFS(node1,node2);
    
    
    
    cout << answer << endl;
  
    return 0;
}

 

 

 

 

 

 

참고 : yabmoons.tistory.com/31