[BOJ] #9789 Friendship Graph

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

---

실버1 난이도라 문제 자체는 그렇게 어렵지 않은데, 그래프를 탐색하는 방법 중 가장 대중적인 DFS와 BFS를 한번에 연습하기 좋은 문제이다. 또한 아예 영어로만 되어있는 문제라 ICPC 대회를 준비하기 위해 영어문제 푸는 연습을 하기 위해 한번 풀어보았다. 

입력에서 주어진 그래프를 구성하고, 해당 그래프에서 A -> B로 갈수있는지 없는지 여부를 판단하여 출력해주면 되는 문제이다. 당연히 A -> B의 입력이 들어올때마다 DFS나 BFS를 돌려 최적화된 visited 배열을 가지고 방문 가능 여부를 판단해주면 된다.

이번 문제를 풀면서 확실히 왜 PS에서 BFS보다 DFS를 더 선호하는지 알 수 있었다. 일단 코드 자체가 굉장히 간단하고, 직관적으로 떠올리기도 쉽다. 또한 BFS와 달리 큐와 같은 추가적인 자료구조를 사용하지 않아도 되며, 실제 수행시간 자체도 좀 더 빨랐다. DFS를 사용하지 않을 이유가 없는 것이다.

해당 문제를 친구는 SCC로 풀었다고도 했었는데 그 방법으로도 한번 풀어보면 좋을 것 같다. 

---

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

#define MAX 2002

using namespace std;

int V,E;
bool visited[MAX];
vector<int> Graph[MAX];

void DFS(int curr) {
    visited[curr] = true;

    for (int next : Graph[curr])
        if (!visited[next]) DFS(next);
}

void BFS(int curr) {
    queue<int> q;
    q.push(curr);
    visited[curr] = true;

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        for (int next : Graph[idx]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> V >> E;
    for (int i=0; i<E; i++) {
        int a,b;
        cin >> a >> b;

        Graph[a].push_back(b);
    }

    int Q;
    cin >> Q;
    for (int i=0; i<Q; i++) {
        int a,b;
        cin >> a >> b;

        fill(visited, visited+V, false);
        //DFS(a);
        BFS(a);
        if (visited[b]) cout << 1 << '\n';
        else cout << 0 << '\n';
    }

    return 0;
}

첫번째 시도가 DFS, 두번째 시도가 BFS에 해당한다. DFS가 메모리도 적게 먹고 수행시간도 0.3초 가량 더 빠르다.