[Java] BOJ 1976번 여행 가자

1976번: 여행 가자

---

풀이

Disjoint Set을 사용하여 우선 그룹별로 묶고 문제의 조건에서 같은 도시를 여러 번 방문할 수 있다고 되어있으므로 입력받은 여행 도시들이 전부 같은 그룹이라면 여행이 가능하므로 "YES"를 출력하고 하나라도 다른 그룹인 도시가 있다면 여행이 불가능하므로 "NO"를 출력하게했습니다.

---

코드

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 Main {
	public static class Edge {
		int from, to;
		
		public Edge(int from, int to) {
			this.from = from;
			this.to = to;
		}
	}
	
	public static int N, M;
	public static int[] parents, cities;
	public static List<Edge> edgeList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;		
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		parents = new int[N + 1];
		cities = new int[M];
		edgeList = new ArrayList<>();
		
		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; ++j) {
				int node = Integer.parseInt(st.nextToken());
				
				if (node == 1) {
					edgeList.add(new Edge(i, j));
				}
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; ++i) {
			cities[i] = Integer.parseInt(st.nextToken());
		}
		
		make();
		
		for (Edge edge : edgeList) {
			union(edge.from, edge.to);
		}
        
		for (int i = 1; i < M; ++i) {
			if (findSet(cities[i]) != findSet(cities[i - 1])) {
				System.out.println("NO");
				System.exit(0);
			}
		}
		
		System.out.println("YES");
	}
	
	public static void make() {
		for (int i = 1; i <= N; ++i) {
			parents[i] = i;
		}
	}
	
	public static int findSet(int a) {
		if (parents[a] == a) {
			return a;
		}
		
		return parents[a] = findSet(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if (aRoot == bRoot) {
			return false;
		}
		
		parents[bRoot] = aRoot;
		return true;
	}
}

---

GitHub - pyo7410/Algorithm: 1일 1커밋을 목표로!