백준 2644 - 촌수계산 - DFS

문제

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

풀이전략

1. 촌수를 계산하는 것은 결국 그래프에서 연결되어있는 정점들과의 관계를 확인하는 것이다. 따라서 DFS로 문제를 해결하는 것이 적합하다.
2. 1촌씩 증가시키며 탐색을 하고 이중 최소 촌수값을 구해야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
int p1, p2;
int a[101][101];
bool ch[101] = {false, };
int res = 2147000000;
// 여기서 L이 촌수가 된다. 
void DFS(int L,int v){
    if(v == p2){
        if(L < res) res = L;
        return;
    }
    for(int i=1; i<=N; i++){
        if(!ch[i] && a[v][i] == 1){
            ch[i] = true;
            DFS(L+1, i);
            // 다른 경로로 가기위해 false로 처리해준다. 
            ch[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    // 두 구해야할 두 사람중 한명은 시작점, 한명은 끝점으로 처리한다. 
    cin >> p1>> p2;
    cin >> M;
    int ta, tb;
    for(int i=1; i<=M; i++){
        cin >> ta >> tb;
        a[ta][tb] = 1;
        a[tb][ta] = 1;
    }
    ch[p1] = true;
    DFS(0, p1);
    /// 아무것도 없을때를 못봄....
    if(res == 2147000000) cout<<-1<<endl;
    else cout<<res<<endl;    

    return 0;
}

소감

이 문제를 보고 바로 DFS임을 떠올릴 수 있어야한다. 또한 문제에서 아무런 관계가 없을때 -1을 출력해야함을 보지 못하였다. 문제를 더 잘 체크해야한다.