[BOJ, C++]#1976_여행 가자, BFS, 그래프 탐색

#1. 문제

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

 

---

 

#2. 풀이

 

1. BFS

[자료구조]#6_그래프

BFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 인접한 정점들을 우선 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현됩니다.

 

2. 시작 정점을 기준으로 BFS 수행, 그리고 방문 여부 체크!

1. 먼저, 주어진 경로의 시작 정점으로부터 BFS를 수행합니다. 이때, 방문한 정점들에 대하여 방문 여부를 체크해 줍니다.
2. 주의할 점으로 "같은 도시를 여러 번 방문해도 된다"는 의미를 오해하면 안 됩니다. 어떠한 정점에 대하여 방문 여부 체크하면 해당 정점을 다시 방문 못하는 거 아니야?라고 오해할 수 있습니다. 다만, BFS를 통해 현재 정점에 인접한 가능한 모든 경로에 대하여 첫 방문에 이미 탐색을 진행했다는 의미로 해석해야 합니다.
3. 그리고, 경로 상의 도시들에 대하여 방문 여부를 체크하고, 모두 방문했다면 "YES", 방문하지 않았다면 "NO"를 출력해 줍니다.

 

---

 

#3. 코드

@@ -0,0 +1,95 @@
/*
    @링크: https://www.acmicpc.net/problem/1976
*   @문제: 여행 가자
*   @설명
        1. BFS 활용
        2. 같은 도시를 여러 번 방문해도 된다 -> 이미 방문한 도시의 방문 여부를 체크하지 않아도 된다 (X)
        3. BFS를 통해 특정 정점을 방문했다면, 해당 도시로부터 가능한 모든 경로에 대하여 '이미' 탐색이 진행중이다.
           따라서, 같은 도시를 여러번 방문해도 된다는 다시 말해 특정 정점을 경유하는 모든 경로를 통해 도착 정점에만
           도착하면 된다!라는 의미이다. 방문 여부 체크는 단순히 같은 작업을 반복하지 않기 위해서다!
          
*/


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

typedef pair<int,int> p;

int N, M;
vector<vector<int>> cities;
vector<int> travel;

void bfs()
{
    vector<bool> visited(N+1, false);
    queue<int> q;

    q.push(travel.front());
    visited[travel.front()] = true;

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

        for(int i=1; i<=N; ++i)
        {
            if(cities[cur][i] != 0 && !visited[i])
            {
                visited[i] = true;
                q.push(i);
            }
        }
    }

    for(int i=0; i<M; ++i)
    {
        if(!visited[travel[i]])
        {
            cout << "NO";
            return;
        }
    }

    cout << "YES";

}

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

    cin >> N;

    //@resize
    cities.resize(N+1, vector<int>(N+1));

    cin >> M;

    travel.resize(M);

    //@도시 연결 여부
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<= N; ++j)
        {
            cin >> cities[i][j];
        }
    }

    //@여행 계획
    for(int i=0; i<M; ++i)
    {
        cin >> travel[i];
    }

    bfs();

    return 0;
}

 

---