[C/C++] 백준 1976번 - 여행 가자 (BFS)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int N, M, x;
int city[201][201];
bool visit[201];
bool flag;
vector<int> check_list;
queue<int> q;

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

    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> city[i][j];

    for (int i = 1; i <= M; i++)
    {
        cin >> x;
        check_list.push_back(x);
    }

    q.push(check_list[0]);

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

        visit[now] = true;

        for (int i = 1; i <= N; i++)
        {
            // 갈수있고 방문한적이없는 도시라면
            if (city[now][i] == 1 && !visit[i])
                q.push(i);
        }

    }

    flag = true;

    for (int i = 0; i < check_list.size(); i++)
    {
        if (!visit[check_list[i]])
        {
            flag = false;
            break;
        }
    }

    cout << (flag ? "YES" : "NO");
}

 

풀이 방법

여행할 도시들이 이어져있는지 판단하는 문제입니다.

첫번째로 여행할 도시를 큐에 넣고 BFS를 돌려 방문한 도시들을 check하고 여행할 도시들이 모두 방문표시 되어있는지 판단을 하여 답을 출력하였습니다.

 

www.acmicpc.net/problem/1976

1976번: 여행 가자