백준 1976 - 여행 가자

백준 1976 - 여행 가자

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

나도 여행가고 싶다.

★ 풀이

여행지를 모두 가기 위해서는 모든 여행지가 연결되어 있어야 한다. 문제에서는 여행지의 연결 정보를 제공한다.

그렇다면 이 연결 정보들을 이용해 유니온 파인드 자료구조를 통해서 그룹화 시키고, 마지막에 모든 여행지의 ROOT노드의 일치 여부를 판별해주면, 여행의 가능 여부를 판별해 줄 수 있다.

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int parent[]; static int rank[]; static int n,m; static int plan[]; public static void main(String[] args) throws IOException { n = Integer.parseInt(br.readLine()); m = Integer.parseInt(br.readLine()); plan = new int[m]; parent = new int[n + 1]; rank = new int[n + 1]; for(int i = 1; i<=n; i++) { parent[i] = i; } StringTokenizer st; for(int i = 1; i<=n; i++) { st = new StringTokenizer(br.readLine()); for(int j = 1; j<=n; j++) { int cmd = Integer.parseInt(st.nextToken()); if(cmd == 1) { union(i,j); } } } st = new StringTokenizer(br.readLine()); for(int i = 0; i rank[b]) { int tmp = a; a = b; b = tmp; } parent[a] = b; if(rank[a] == rank[b]) rank[a]++; } static int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } }

from http://sweet-smell.tistory.com/134 by ccl(A) rewrite - 2021-12-05 19:00:38