[백준 2644번] [DFS] 촌수계산

이 문제의 경우에서 기본적인 접근방법은, 자신을 기준으로 위로 올라가는 방향이든 아래로 내려가는 방향이든 구분하지 않고 이동을 한번 하면 촌수가 1 증가한다는 것을 이용하여 그래프를 활용하여 촌수를 계산할 수 있다는 것을 인지하고 풀면 된다.

 

처음에는

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

using namespace std;
int visited[101] = {0};

int dfs(int start, int end, int (&data_store)[101][101]){
    if(start == end) return 0;
    if(visited[start] == 1) return 0;
    else{
        int count = 0;
        visited[start] = 1;
        for(int i = 0; i < 101; i++){
            if(visited[i] != 1){
                if(data_store[start][i] == 1){
                    if(i == end){
                        return 1;
                    }
                    else{
                        int check_num = dfs(i, end, data_store);
                        if (check_num > 0){
                            return 1 + check_num;
                        }
                    }      
                }
            }
            
        }
        return -1; // 안나온 경우
    }
}

int main(void){
    int n;
    cin >> n; // 사람의 수

    int check_people1, check_people2;
    cin >> check_people1 >> check_people2;
    int data_store[101][101] = {0};

    int node_num;
    cin >> node_num;

    for(int i = 0; i < node_num; i++){
        int temp;
        cin >> temp;
        int push_data;
        cin >> push_data;
        data_store[temp][push_data] = 1;
        data_store[push_data][temp] = 1;
    } // data_store

    cout << dfs(check_people1, check_people2, data_store);

    return 0;
}

이런 방식으로 처리하였다. 어느 시점에서 목표가 나올지 모르는 상황이기에 이러한 방법을 택하였으나 코드를 다시 복기하는 중에 매우 비효율적인 풀이방법이라는 것을 인식하게 되었다.

 

위 방식의 경우에는, 표적이 나올 때에만 1이 나오게 해서 그 경우에만 계속해서 숫자들을 더하도록 하게끔 하였는데 그러지 말고 애초에 함수의 parameter안에 몇 단계가 들어갔는지를 표시해주는 것이 훨씬 효율적이다. 또한, visited의 경우에는 0,1로 표시하는 것도 물론 나쁘지는 않지만 bool로 하는 것이 훨씬 더 직관적이다.

 

좋은 코드의 예시는 다음과 같다.

#include <cstdio>
using namespace std;

int arr[101][101] = { 0, };
bool visit[101] = { false, };
int n, ans = 0;

void dfs(int me, int find, int num) {
    visit[me] = true;

    if (me == find) {
        // 만약 찾았다면 지금까지 누적된 촌수를 저장하고 return
        ans = num;
        return;
    }

    for (int i = 1; i <= n; i++) {
        // 부모나 자식을 촌수를 올리며 순회해본다
        if (arr[me][i] == 1 && !visit[i]) {
            dfs(i, find, num + 1);
        }
    }

    return;
}

int main() {
    int a, b, m;
    scanf("%d", &n);
    scanf("%d %d", &a, &b);
    scanf("%d", &m);

    for (int i = 0; i < m; i++) {
        int parent, child;
        scanf("%d %d", &parent, &child);
        arr[child][parent] = 1;
        arr[parent][child] = 1;
    }

    dfs(a, b, 0);

    ans == 0 ? printf("-1\n") : printf("%d\n", ans);

    return 0;
}

계속 피드벡 해야한다..

종만북에서 코드를 읽어보면서 피드벡을 해보자..