[백준] 단계별로 풀어보기(단계:30, 유니온 파인드,JAVA)1976번, 여행 가자

문제 링크

1976번: 여행 가자

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

유니온 파인드

 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조

Union : 집합끼리 합치는 연산

Find : 집합의 원소가 어디에 속해있는지 확인하는 연산

Union Find - 나무위키

이 문제에 핵심은

1. 1~N까지 도시번호가 주어집니다.

2. 도시가 연결된 것은 양방향입니다.

3. 1은 연결된 것이고 0은 연결되지 않은 것입니다.

4. 입력되는 여행 계획으로 이동할 수 있으면 YES, 없으면 NO를 결과로 출력합니다.

 

예제입력1에서 유니온파인드가 어떻게 진행되는지 보여드리겠습니다.

 

※저는 합집합을 진행할 때 집합의 루트 노드가 더 작은 곳을 루트 노드로 하였습니다.

 

 

빨간색 : 해당 원소의 루트 노드

1	2	3
1	2	3

 

입력값 : 0 1 0

해석 : 도시 1에서 도시 2로 방문 가능

1	2	3
1	1	3

도시 1과 도시 2의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 0 1

해석 : 도시 2에서 도시1, 3으로 방문 가능

1	2	3
1	1	1

도시 2에서 도시 1, 3의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 0 1 0

해석 : 도시 3에서 도시 2으로 방문 가능

1	2	3
1	1	1

도시 3와 도시 2의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

방문 계획 : 1 2 3

해석 : 도시1 -> 도시2 -> 도시3

1	2	3
1	1	1

 

도시1 -> 도시2의 루트 노드를 비교하면 같기 때문에 이동 가능

도시2 -> 도시3의 루트 노드를 비교하면 같기 때문에 이동 가능

도시1 -> 도시2 -> 도시3순으로 여행 가능

출력 : YES

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 n,m과 명령어에 대한 정보를 저장합니다.
• 도시에 입력값에 따라 union함수를 실행하였습니다.
• BufferedWriter에 여행계획으로 isCheck의 따라 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find는 재귀탐색을 이용하여 루트 노드의 값을 찾는 함수입니다.
• union은 두 집합의 루트 노드의 값을 얻어서 더 작은 값으로 통합하는 함수입니다.
• isCheck은 두 집합의 루트 노드의 값이 같은지 확인하여 교집하는지 확인하는 함수입니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	static int N,M;
	static int[] node;	//도시의 루트 노드 저장하는 배열
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		node = new int[N+1];
        	//1~n번의 도시 루트 노드 초기화
		for(int i=1;i<=N;i++)
			node[i] = i;
            	//입력되는 도시 방문
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=1;j<=N;j++) {
				int temp = Integer.parseInt(st.nextToken());
				if(temp==1)	//합집합 
					union(i,j);
			}
		}
        	//방문 계획에 맞게 이동 가능한지 확인
		st = new StringTokenizer(br.readLine()," ");
		int a = Integer.parseInt(st.nextToken());
		for(int i=1;i<M;i++) {
			int b = Integer.parseInt(st.nextToken());
			if(!isCheck(a, b)) {	//이동 불가능
				bw.write("NO");
				break;
			}
			if(i==M-1)		//이동 가능
				bw.write("YES");
		}
		bw.flush();	//결과 출력
		bw.close();
		br.close();
	}
    	//루트 노드 찾는 함수
	static int find(int n) {
		if(n==node[n])
			return n;
		return node[n] = find(node[n]);
	}
    	//루트 노드를 비교하여 작은 값을 기준으로 변경하는 함수
	static void union(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x!=y) {
			if(x>y)
				node[x] = y;
			else
				node[y] = x;
		}
		return;
	}
    	//a,b에 대해서 루트노드가 동일한지 확인하는 함수
	static boolean isCheck(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x!=y)
			return false;
		else
			return true;
	}
}