boj 1976 여행 가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

두 가지 방법으로 해결하였습니다. 하나는 union-find를 이용한 방법, 하나는 dfs를 이용한 방법입니다.

 

먼저 union-find 방법입니다.

입력에서 인접한 도시의 정보가 주어집니다.

(i, j)가 0이면 인접X, 1이면 인접한 도시입니다.

1이 주어질때마다 union-find로 parent를 갱신해줍니다.

 

마지막으로 M개 도시의 parent가 모두 같으면 YES, 하나라도 다르면 NO입니다.

 

 

[Union-find]

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> travel;
int parent[201];
int N, M;
 
void init() {
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
}
 
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}
 
void func() {
    int x = find(travel[0]);
    for (int i = 1; i < M; i++) {
        int y = find(travel[i]);
 
        if (x != y) {
            cout << "NO\n";
            return;
        }
    }
 
    cout << "YES\n";
}
 
void Union(int x, int y) {
    if (x > y) swap(x, y);
    
    int a = find(x);
    int b = find(y);
 
    parent[b] = a;
}
 
void input() {
    int k;
    cin >> N >> M;
    init();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> k;
            if (k) {                
                Union(i, j);
            }
        }
    }
    
    for (int i = 0; i < M; i++) {
        cin >> k;
        travel.push_back(k);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

그 다음은 dfs를 이용한 방법입니다.

위와 마찬가지로 0이면 인접X, 1이면 인접한 정점이므로 벡터에 넣어줍니다.

그 다음 M개의 도시 중 첫번째 도시를 루트로 dfs를 돌려줍니다. (이 때 방문체크를 한 것을 이용합니다.)

 

마지막으로 dfs로 순회하면서 M개의 도시를 모두 방문하였는지 체크해줍니다.

하나라도 방문을 하지 않았으면 연결이 안되어있다는 말이므로 NO를 출력해줍니다.

M개의 도시를 모두 방문하였으면 YES를 출력합니다.

 

 

[dfs]

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> graph[201], travel;
bool visit[201];
int N, M;
 
void func() {
    for (int i = 0; i < M; i++) {
        int x = travel[i];
        if (visit[x]) continue;
 
        cout << "NO\n";
        return;
    }
 
    cout << "YES\n";
}
 
void dfs(int v) {
    visit[v] = true;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
 
        if (visit[next]) continue;
        dfs(next);
    }
}
 
void input() {
    int k;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> k;
            if (k) graph[i].push_back(j);
        }
    }
 
    for (int i = 0; i < M; i++) {
        cin >> k;
        travel.push_back(k);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dfs(travel[0]);
    func();
 
    return 0;
}