[Baekjoon] 1976_여행 가자

Gold IV

문제(출처: https://www.acmicpc.net/problem/1976)

---

< 여행 가자 >

 

문제 풀이 

 

Union-Find 알고리즘을 통해 같은 집합인지 확인해서 여행의 가능 여부를 판단했다.

 

 

 my solution (Java)

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

public class _1976_ { // 여행 가자
	static int arr[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		arr = new int[n + 1];
		for(int i=0; i<n+1; i++) {
			arr[i]=i;
		}

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());
				if (x == 1) {
					int a = find(i + 1);
					int b = find(j + 1);

					if (a > b)
						arr[a] = b;
					else
						arr[b] = a;
				}
			}
		}

		st = new StringTokenizer(bf.readLine());
		int result = find(Integer.parseInt(st.nextToken()));
		boolean flag = false;

		for (int i = 1; i < m; i++) {
			int num = find(Integer.parseInt(st.nextToken()));
			if (result != num) {
				flag = true;
				break;
			}
		}

		if (!flag) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

	private static int find(int i) {
		if (arr[i] == i)
			return i;
		return arr[i] = find(arr[i]);
	}

}

 

Main

변수)
n : 도시의 수
m : 여행 계획에 속한 도시의 수
arr : 집합
result : 여행 계획에 속한 첫 번째 도시의 집합 번호 
flag : 가능 여부

 

- 도시의 수(n), 여행 계획에 속한 도시의 수(m) 입력

- 집합을 구분하기 위해 배열을 index 번호와 동일하게 초기화

- 도시의 연결 정보 입력

: 1이면 연결된 것이므로 같은 집합임을 표시

- 여행 계획에 속한 도시 중에서 첫 번째 도시의 집합을(result) 먼저 구함

- 여행 계획에 속한 도시 탐색

: 위에서 구한 집합과 나머지 여행 계획에 속한 도시의 집합이 다르면 불가능하므로 중지

- flag 여부에 따라 정답 출력

 

find

- arr[i]와 i가 같다면 부모 노드 이므로 i 반환

- arr[i]와 i가 같지 않다면 부모 노드가 아니므로 다시 find를 호출하며 나중에 같은 일을 반복하지 않도록 값 update

---

---