백준 1976 여행 가자

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

※선행해야 할 알고리즘 : Disjoint-set(Union-Find), BFS/DFS

Algorithm : 그래프를 입력 후, 마지막에 입력한 여행 코스를 갈 수 있는지 없는지 확인하여 출력하는 것

방법은 두가지가 있다. 그래프 전체를 입력받아 우선탐색을 실시하는 방법과 그래프를 입력받았을 때 연결된 부분을 union한 후 find해나가는 방식(즉, BFS/DFS or Union-Find로 풀면된다.)

먼저 Union-Find이다.(DFS방식은 풀이를 따로 작성하지 않았으며 소스로 풀이를 참고바랍니다.)

1. 그래프를 입력받을 때, 연결된 부분에 대해서는 바로 Union을 해준다.

2. 그래프 입력이 다 되면 m개의 여행 계획에 속한 도시들을 find해주면 된다.

단, find를 할 때 루트를 기준으로 루트가 포함되어 있지 않다면 중간에 갈 수 없다는 것을 의미한다.

여행 코스 중 첫 도시를 find하여 나온 값을 루트로 잡고 find할 때마다 루트가 나오지 않는다면 연결되어 있지 않은 것이다.

3. 1~2를 Disjoint-set를 활용하여 풀면 다음과 같다.

//disjoint-set Algorithm //kuklife.tistory.com #include<cstdio> #include<vector> using namespace std; vector<int> set; int find(int x) { if (x == set[x]) return x; else return set[x] = find(set[x]); } void Union(int x, int y) { x = find(x); y = find(y); set[x] = y; } int main() { int n, m, x, y; scanf("%d %d", &n, &m); for (int i = 0; i <= n; i++) set.push_back(i); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &x); if (x) Union(i, j); } } scanf("%d", &x); y = find(x); for (int i = 1; i < m; i++) { scanf("%d", &x); if (y != find(x)) { printf("NO\n"); return 0; } } printf("YES\n"); return 0; }

//DFS //kuklife.tistory.com #include <cstdio> int course[1001], n, m, t, check; bool ch[201], G[201][201]; void dfs(int x) { ch[x] = 1; for (int i = 1; i <= n; i++) if (G[x][i] && !ch[i]) { ch[i] = 1; dfs(i); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &G[i][j]); for (int i = 0; i < m; i++) scanf("%d", &course[i]); dfs(course[0]); for (int i = 1; i < m && !check; i++) if (!ch[course[i]]) check = 1; printf(check ? "NO" : "YES"); return 0; }