백준 2644 촌수계산, c++

 

 

처음 작성한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

vector<int> person[101];
vector<int> result_dfs;
bool visit[101];
int start, stop;
int num = 0;

void dfs(int x){
    visit[x] = true;
    result_dfs.push_back(x);
    num = x;
    
    if(x == stop){
        return;        
    }
 
    for (int i=1; i<=person[x].size(); i++){
        if(!visit[person[x][i]]){ //방문하지 않은 곳만 탐색
            dfs(person[x][i]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    cin >> start >> stop;
    
    int m;
    cin >> m;
    
    int x, y;
    for(int i=1; i<=m; i++) {
        cin >> x >> y;
        person[x].push_back(y); //양방향 간선처리
        person[y].push_back(x); //양방향 간선처리
    }
    
    for (int i=1; i<=n; i++){
        sort(person[i].begin(), person[i].end()); // 낮은 숫자부터 탐색.
    }    
    memset(visit, false, sizeof(visit));    
    dfs(start);
    
    if(num == stop)
        cout << result_dfs.size()-1;
    else
        cout << "-1";
    
    return 0;
}

 

 

 

하지만 틀렸다는 결과가 나왔다.

어딘가 오류가 있는 것 같아 고쳐야했다.

dfs든 bfs든 사용해도 되나 구현에 문제가 있었다.

dfs, bfs 알고리즘의 원리를 제대로 이해하지 못하고 코드를 막 적용했던 것이 문제 였다.

문제를 잘 읽고 원하는 것을 출력하도록 해야 했다.

모든 정점을 탐색하되 그 탐색 순서를 출력하는 문제인지(그냥 탐색만 하면 되는 문제인지), 시작점과 끝점이 정해져있고 그 사이의 최단 거리를 구하는 문제인지, 양방향그래프인지 단방향 그래프인지 문제에 따라 잘 파악하고 코드를 구현해야 겠다.

 

문제는 bfs 알고리즘을 사용했고, visited 배열을 통해 거리를 세서 구현완료하였다.