[BOJ 2644] 촌수계산

문제 출처

https://www.acmicpc.net/problem/2644

단순 bfs구현 문제이다.

ret배열이 0이라면 관계가 없으므로 -1을 출력하고 0이 아니면 해당 값을 출력하도록 했다.

bfs / dfs를 언제 사용하는지 감이 잘 안왔었는데 간단히 정리하면

bfs를 이용하는 경우

1. 시작 지점에서 가장 가까운 것을 구하고 싶은 경우

2. 탐색 범위 자체는 넓지만 어느정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우

3. 탐색 범위가 굉장히 넒으며 dfs를 사용할 때 스택이 대량으로 사용될 경우 이다.

반면 dfs를 이용하는 경우는

1. 모든 경로를 탐색하고 결과를 확인해야 하는 경우

2. 문자열 등을 탐색할 때 '사전 순서로 앞에오는 것'처럼 앞에서 검색해서 찾는 것이 빠를 경우 이다.

즉, 탐색 범위가 넓은 경우와 전체 탐색을 하지 않아도 될 경우는 bfs를 이용하고 전체 탐색이 필요하거나 순차적으로 찾을 필요가 있는 경우는 dfs를 사용하는 것이 좋다.

소스

//
//  main.cpp
//  BOJ_2644
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
 
#include<iostream>
#include<queue>
#define MAX 101
 
using namespace std;
int n, src, dest, m, adj[MAX][MAX], ret[MAX];
 
int main(int argc, const char * argv[]) {
    cin >> n >> src >> dest >> m;
    for (int i = 0; i < m; i++) {
        int x = 0, y = 0;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = 1;
    }
    
    queue<int> q;
    q.push(src);
    
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (adj[now][i] == 0 || ret[i] != 0)
                continue;
            ret[i] = ret[now] + 1;
            q.push(i);
        }
    }
    cout << (ret[dest] == 0 ? -1 : ret[dest]) << endl;
    return 0;
}