[백준(BOJ)] 2644번: 촌수계산 (DFS/BFS, C++)

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;
int BFS(int target1, int target2, deque<int> *graph, bool *visited, deque<int> *child){
    queue<int> q;
    visited[target1] = true; // check visited
    q.push(target1);
    (*child)[target1] = 0;
    while(!q.empty()){
        int current = q.front(); // get front element from queue

        q.pop(); // pop front element
        for(int num: graph[current]){
            if(visited[num] == false){
                q.push(num);
                visited[num] = true;
                (*child)[num] = (*child)[current] + 1;

                if(num == target2) return (*child)[num];
            }
        }
    }
    return -1; //queue가 empty가 되어도 num == target2인 조건이 없어서 리턴하지 못함 == target2 찾지 못함 == target2가 연결되어 있지 않음
}

int main(){
    int n, m, target1, target2; // n: # of nodes, m: # of edges

    scanf("%d", &n);
    scanf("%d %d", &target1, &target2);
    scanf("%d", &m);

    deque<int> graph[n];
    deque<int> child[n]; // parent - child
    bool visited[n]; // check if visited

    fill(visited, visited+n, false);

    for(int i=0; i<m; i++)
    {
        int u,v, result; 

        scanf("%d %d", &u, &v);

        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    int result = BFS(target1-1, target2-1, graph, visited, child);

    printf("%d\n", result);
}

 

 

📝 문제풀이 과정

---

#include <stdio.h>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;
int BFS(int target1, int target2, deque<int> *graph, bool *visited, deque<int> *child){
    queue<int> q;
    visited[target1] = true; // check visited
    printf("[+] %d VISITED\n", target1);
    q.push(target1);
    (*child)[target1] = 0;
    while(!q.empty()){
        int current = q.front(); // get front element from queue

        q.pop(); // pop front element
        for(int num: graph[current]){
            if(visited[num] == false){
                q.push(num);
                visited[num] = true;
                (*child)[num] = (*child)[current] + 1; printf("%d: %d\n", num, (*child)[num]);

                printf("[+] %d VISITED\n", num);
                if(num == target2) return (*child)[num];
            }
        }
    }
    return -1; //queue가 empty가 되어도 num == target2인 조건이 없어서 리턴하지 못함 == target2 찾지 못함 == target2가 연결되어 있지 않음
}

int main(){
    int n, m, target1, target2; // n: # of nodes, m: # of edges

    scanf("%d", &n);
    scanf("%d %d", &target1, &target2);
    scanf("%d", &m);

    deque<int> graph[n];
    deque<int> child[n]; // parent - child
    bool visited[n]; // check if visited

    fill(visited, visited+n, false);

    for(int i=0; i<m; i++)
    {
        int u,v, result; 

        scanf("%d %d", &u, &v);

        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    int result = BFS(target1-1, target2-1, graph, visited, child);

    printf("%d\n", result);
}

• graph: parent, child 모두 각자의 deque 공간에 서로를 넣는다. 그래야 그래프의 연결성으로 BFS 탐색을 이어갈 수 있다.
• child: 각 노드의 parent와 child의 촌수 관계를 나타낸다. 시작 노드 기준으로 BFS 탐색 순서에 따라 촌수가 계산된다.
• 0번 인덱스부터 값을 넣어서, 입력받는 값-1로 BFS를 진행했다.
• visited는 초기에 false로 초기화하고, 반복문을 돌면서 해당 노드에 방문할 때마다 true로 값을 할당한다.
• 노드에 대한 촌수는, 자신을 부른 current 노드 촌수 + 1로 값을 할당한다.
  • 아래의 촌수 계산 경우들에 대한 target1 기준 촌수를 모두 계산할 수 있다.
• target2와 num이 같다면 child[num]을 리턴한다.
• 만약 while문에서 나왔다면, queue가 empty가 된 것이고, empty가 될 때까지 리턴하지 못한, 즉 target2를 방문하지 못한 것이다.
  • 따라서 촌수 관계가 아니므로 -1을 리턴한다.

 

 

촌수 계산

• 부모 - 자식: 1촌
• 형제: 1촌
• 나 자신: 0촌 => target1 == target2인 경우 그냥 나오게 되므로 result = 0
• 나와 아버지의 형제: 3촌

👏 결과

---