[BOJ] 백준 2644번 촌수계산 (C++ 코드)

🧨 백준 2644번 - 촌수계산

문제 난이도 : 실버2

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

2644번: 촌수계산

🧨 알고리즘 선택 및 C++ 코드

DFS를 쓰는 줄 알았는데 코드에 감이 안 잡혀서 더 생각해봤더니 BFS를 활용한 문제였다. 너비우선탐색으로 깊이를 카운팅했다. 정점(첫 노드)에서 내가 원하는 사람까지 가는 깊이만 카운팅하려 했는데 조건문 쓰는 게 더 복잡해서 그냥 다 계산했다. 입력받은 start 사람에서 모든 사람들까지의 깊이를 카운팅해 depth 배열에 저장했다. 음 생각보다 쉽지 않은 접근이었는데 이런 방식의 문제는 앞으로 많이 나올 거 같다..

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

int n, x, y, m;
int isMarked[101] = {false};

void BFS(int G[101][101], int start, int end) {
    int isMarked[101] = {false};
    int isinQueue[101] = {false};
    int depth[101] = {0};
    
    queue<int> q;
    q.push(start);
    isinQueue[start] = true;
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        isMarked[current] = true;
        
        for(int i = 1; i < n + 1; i++) {
            if(!isMarked[i] && !isinQueue[i] && G[current][i]) {
                q.push(i);
                isinQueue[i] = true;
                depth[i] = depth[current] + 1;
            }
        }
    }
    if(depth[end] == 0) cout << -1;
    else cout << depth[end];
    return;
}

int main() {
    cin >> n;
    cin >> x >> y;
    cin >> m;
    
    int G[101][101] = {0};
    for (int i = 0; i < m; i++) {
        int parent, child;
        cin >> parent >> child;
        G[parent][child] = 1;
        G[child][parent] = 1;
    }

    BFS(G, x, y);

    return 0;
}