백준 1976번 : 여행 가자

 문제

www.acmicpc.net/problem/1976

1976번: 여행 가자

1976 여행 가자

 

 구현 방법

 union-find로 구현해주었습니다.

도시의 수 만큼 root 배열인 parents 배열을 만들어주고 도시 집합을 생성합니다.

연결 정보를 받아와 1이면 union(x, y) 로 집합을 합쳐줍니다.

모든 연결이 끝난 후 여행 계획을 받아와 루트 노드를 찾아 같으면 연결되었으므로 "YES" 출력, 다르면 비연결이므로 "NO"를 출력해줍니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class B1976_여행가자 {
	static int N, M;
	static int[] parents;
	static void makeSet() {
		for (int i=1;i<=N;i++) {
			parents[i] = -1;
		}
	}
	
	static int findSet(int x) {
		if (parents[x]<0) return x;
		return parents[x] = findSet(parents[x]);
	}
	
	static void union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot==bRoot) return;
		parents[bRoot] = aRoot;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		parents = new int[N+1];
		M = Integer.parseInt(br.readLine());
		makeSet(); // 집합 만들기
		for (int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=1;j<=N;j++) {
				int to = Integer.parseInt(st.nextToken());
				if (to==1) union(i, j); // 1일 때 연결
			}
		}
		boolean flag = true;
		st = new StringTokenizer(br.readLine());
		List<Integer> list = new ArrayList<>();
		while(st.hasMoreTokens()) {
			list.add(Integer.parseInt(st.nextToken())); // 여행 계획 저장
		}
		for(int i=1;i<list.size();i++) {
			if (findSet(list.get(0))!=findSet(list.get(i))) { // 루트 찾아서 같으면 연결, 다르면 비연결
				flag = false;
				break;
			}
		}
		
		if (flag) System.out.println("YES");
		else System.out.println("NO");
	}
}

 

정답!