[백준] 1976번 : 여행 가자

문제

 

 

접근 방식

인접 리스트를 만든 후에 일반적인 그래프 탐색으로 여행 경로를 모두 이동해보면

시간 초과가 발생하기 때문에 여행 경로가 모두 한 사이클에 포함 되는지만 파악하면 된다.

 

이럴 때 효율적인 알고리즘이 유니온 파인드인데

유니온 함수를 이용해 연결된 정점들끼리의 부모를 기록해두고

파인드 함수를 이용해 서로의 최고 조상이 누구인지 확인하여

같은 사이클에 존재하는지 여부를 빠르게 판단할 수 있다.

 

초기에는 각 도시마다 자기 자신을 부모로 초기화하고

주어진 도시 간의 경로를 유니온 함수로 연결한 후에

여행 경로대로 파인드 함수를 사용해 모두 하나의 사이클에 포함되는지 확인한다.

 

풀이

public class Main {

	static int[] parent;

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

		boolean isPossible = true;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		parent = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}

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

			for (int j = 1; j <= n; j++) {
				if (Integer.parseInt(st.nextToken()) == 0) continue;
				union(i, j);
			}
		}

		st = new StringTokenizer(br.readLine());
		int x = find(Integer.parseInt(st.nextToken()));

		for (int i = 1; i < m; i++) {
			if (find(Integer.parseInt(st.nextToken())) != x) {
				isPossible = false;
				break;
			}
		}

		System.out.println(isPossible ? "YES" : "NO");
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) parent[y] = x;
	}

	static int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
}