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

발상 자체가 조금 까다로운 문제이다. (그런 줄 알았는데, 내가 문제를 잘못 읽었다.)

상근이 ( 또 상근이야? )는 여러 나라를 여행할 건데, 최소한의 비행기만을 타고자 한다.

A에서 B로 가는 비행기가 있다고 할 때, B에서 A로 가는 비행기는 한 종류로 취급한다.

 

상근이가 모든 나라로 여행을 가면서도 최소한의 비행기를 타려면 몇 번의 비행기를 타야 하는가?

 

여담이지만, 모든 나라를 돌면서도, 실패할 경우에 무엇을 출력하라는 말이 없는 것을 보니

test case로, 모두 성립할 수 있는 경우의 수만을 주는 것으로 보인다.

그럼 당연히 국가의 수 - 1이 정답이겠지 (...)

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
int visited[1001];
int counted = 0;
int minV = 987654321;
 
void bfs(int start, vector<int> map[])
{
    visited[start] = 1;
    queue<int> Q;
    Q.push(start);
 
    while (!Q.empty())
    {
        int current = Q.size();
 
        counted++;
        for (int i = 0; i < current; i++)
        {
            int cur = Q.front();
            Q.pop();
 
            for (int j = 0; j < map[cur].size(); j++)
            {
                int next = map[cur][j];
 
                if (visited[next] == 0)
                {
                    visited[next]++;
                    Q.push(next);
                }
            }
        }
 
        bool trueOrNot = true;
        for (int i = 1; i <= n; i++)
        {
            if (visited[i] == 0)
            {
                trueOrNot = false;
                break;
            }
        }
 
        if (trueOrNot)
        {
            int sum = 0;
            for (int i = 1; i <= n; i++)
            {
                sum += visited[i];
            }
            if (minV > sum) minV = sum;
            break;
        }
    }
}
 
int main(void)
{
    int num;
    cin >> num;
 
    while (num--)
    {
        vector<int> map[1001];
    
        cin >> n >> m;
        for (int i = 0; i < m; i++)
        {
            int from, to;
            cin >> from >> to;
 
            map[from].push_back(to);
            map[to].push_back(from);
        }
 
        for (int i = 1; i <= n; i++)
        {
            bfs(i, map);
            for (int j = 1; j <= n; j++)
                visited[j] = 0;
        }
        cout << minV - 1 << endl;
 
        minV = 987654321;
   }
}

 

내가 문제를 잘못 이해해서 조금 더럽게 풀었다.

지금 생각해보면 bfs를 for문 안에 넣어서 돌릴 필요도 없었다.

당연히 비행기의 "종류"는, 방문한 나라 숫자만큼을 탈 수밖에 없을 테니까.