백준 1976 - 여행 가자(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1976

1976번: 여행 가자

분리 집합과 그래프 탐색을 이용해 푸는 문제였습니다.

연결된 정점들을 줬을 때, 주어진 길로 여행을 할 수 있는지 확인하는 문제입니다.

 

예제 입력을 봤을 때, 

1 -> 2

2 -> 1, 3

3 - > 2

와 같이 연결되어 있습니다.

또한, 출발지와 목적지를 여러개로 나눠서 생각해보면, 1 -> 2와 2 -> 3을 확인할 수 있습니다.

따라서, (1, 2) + (2, 3)으로 나눠서 구해주면 됩니다.

 

예를 들어, ABACA로 여행을 한다고 하면,

(A, B) + (B, A) + (A, C) + (C, A) 로 나눠서 구해주면 될 것입니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
vector<int> connect[201];
int check[201];
int fin[1001];

bool bfs(int start, int finish){
    queue<int> q;
    q.push(start);
    check[start] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(finish == x) return true;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] != 0) continue;
            check[xx] = 1;
            q.push(xx);
        }
    }
    return false;
}

bool travel(){
    for(int i = 1; i < M; i++){
        memset(check, 0, sizeof(check));
        if(!bfs(fin[i], fin[i+1])) return false; 
    }
    return true;
}

void solve(){
    if(travel()) cout << "YES";
    else cout << "NO";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            int x;
            cin >> x;
            if(x == 1) {
                connect[i].push_back(j);
                connect[j].push_back(i);
            }
        }
    }
    for(int i = 1; i <= M; i++) cin >> fin[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요