[BOJ] 여행 가자 - 1976

📃 문제

[BOJ 1976] 여행 가자 🔗링크

동혁이는 친구들과 함께 여행을 가려고 한다.
한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다.
동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자.
물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다.
예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고,
동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다 ... (생략)

• 조건
  1. 도시의 수 N : N ≦ 200
  2. 여행 계획한 도시의 수 M : M ≦ 1000
  3. 도시의 연결 정보 i,j : 1,0 (i번 도시와 j번 도시의 연결 여부)

🧠 풀이

✏️ g[N] : 각 도시의 연결 여부 (group 변수로 연결이 독립되었는지 판단)
✏️ i,j 입력에 대한 경우의 수
1. i,j 도시 모두 연결되어있지 않은 경우 : 새로운 group을 부여하여 연결됨을 표시.
2. i,j 도시 중 1곳만 연결된 경우 : 같은 group을 부여하여 연결됨을 표시.
3. i,j 도시 같은 group으로 연결된 경우 : continue
4. i,j 도시 다른 group으로 연결된 경우 : 더 낮은 group (min(g[i], g[j]))으로 모두 변경.

#include <iostream>
#include <algorithm>

using namespace std;

int g[201] = {0,};

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N,M,linked,city;
    int group = 0, can_travel = 1;
    
    
    cin >> N >> M;
    
    for(int st=0; st<N; st++){
        for(int end=0; end<N; end++){
            
            cin >> linked;
            
            if(linked){
                
                if(g[st] && g[end]){
                    if(g[st] == g[end]) continue;
                    else{
                        int find_group = min(g[st], g[end]);
                        
                        for(int city=0; city<=end; city++)
                            if(g[city] == find_group)   g[city] = group;
                    }
                }
                
                else if(g[st] == 0 && g[end] == 0){
                    group++;
                    g[st] = group;
                    g[end] = group;
                }
                
                else if(g[st])      g[end] = g[st];
                else if(g[end])     g[st] = g[end];
            }
        }
    }
    
    for(int i=0; i<M; i++){
        
        cin >> city;
        
        if(i==0)
            group = g[city-1];
        
        else if(can_travel && group != g[city-1])
            can_travel = 0;
    }
    
    if(can_travel)  cout << "YES";
    else            cout << "NO";
    
    return 0;
}