[Backjoon] 촌수계산

한동안 그래프 탐색 문제를 다뤄보지 않아서 복습겸, C++ 공부겸 기본적인 DFS 문제를 풀어봤다. 백준 2644번 촌수계산 문제는 인접 리스트 형태의 자료구조에서 DFS를 통해서 노드의 연결 깊이를 계산하는 문제였다. 인접 리스트이기 때문에 vector를 사용해서 풀었는데 파이썬 보다는 코드가 길어지는 경향이 있다. 아래는 소스코드이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int search(int searchStart, int searchEnd, vector<vector<int>> graph, bool visited[101], int count) {
    if (searchStart == searchEnd) return count;
    
    int answer = -1;

    visited[searchStart] = true;
    for (int i = 0; i < graph.at(searchStart).size(); ++i) {
        if (!visited[graph.at(searchStart).at(i)]) {
            answer = max(search(graph.at(searchStart).at(i), searchEnd, graph, visited, count+1), answer);
        }
    }
    return answer;
}

int main() {

    bool visited[101] = {false};
    vector<vector<int>> graph;

    int famliyCount;
    cin >> famliyCount;

    int searchStart, searchEnd;
    cin >> searchStart >> searchEnd;

    int nodeCount;
    cin >> nodeCount;

    for (int i = 0; i <= famliyCount; ++i) {
        vector<int> temp;
        graph.push_back(temp);
    }

    for (int i = 0; i < nodeCount; ++i) {
        int nodeStart, nodeEnd;
        cin >> nodeStart >> nodeEnd;

        graph.at(nodeStart).push_back(nodeEnd);
        graph.at(nodeEnd).push_back(nodeStart);
    }

    int answer = search(searchStart, searchEnd, graph, visited, 0);
    cout << answer << endl;

    return 0;
}