[백준] 9372번 상근이의 여행 (C++)

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

 

 

이 문제는 N개의 국가와 M개의 비행기의 종류가 주어지고 국가와 비행기를 연결하는 그래프가 관계가 주어진다.

 

이때 최소한의 비행기를 타서 모든 국가를 여행을 할때 비행기의 개수를 출력하는 문제이다.

 

 

비행기의 개수가 최대 2000개이기 때문에 N개에서부터 깊이 우선 탐색을 통해서 갈 수 있는 모든 비행기의 개수를 더해주었다. 이때

갈 수 있는 국가에 방문체크를 하여 증가한 개수를 출력해주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int T, N, M;
vector<vector<int>> v(1001);
bool visited[1001];
int cnt;

void dfs(int Node) {
    visited[Node] = true;

    for(auto next : v[Node]) {
        if(!visited[next]) {
            cnt++;
            dfs(next);
        }
    }
}

void solve() {
    int answer = 0;
    cnt = 0;

    for(int i = 1; i <= N; i++) {
        dfs(i);
        answer += cnt;
        cnt = 0;
    }

    cout << answer << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> M;

        memset(visited, 0, sizeof(visited));
        v.clear();
        v.resize(1001);

        for(int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }

        solve();
    }
}

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

    input();
}