백준 1976번: 여행 가자 [JAVA]

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

• 풀이

두가지 방법으로 해결하였다.

1. Union Find 사용

Union 함수와 Find 함수를 만들어서 이어지는 지역끼리 부모가 같도록 만들어주었다.

여행 계획에서 부모가 다른 지역이 나타나면 NO를 출력한다.

1. ArrayList 사용

ArrayList에 연결된 지역을 각각 담아주었다.

여행 계획에 나타나는 지역마다 BFS를 이용해 연결되는지 확인하고 그렇지 않다면 NO를 출력한다.

메모리와 시간 모두 Union Find 방법을 사용한 것이 효율적이었다.

• 코드

1. Union Find 사용

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

public class Main {
	static int N, M;
	static int parent[];
	
  // 부모찾기
	static int find (int x) {
		if (x == parent[x]) return x; // 루트 노드
		return parent[x] = find(parent[x]);
	}
	
	// 부모 합치기
	static void union (int x, int y) {
		x = find(x);
		y = find(y);
		if (x!=y) {
			if (x>y) parent[x] = y;
			else parent [y] = x;
		}
	}

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(bf.readLine());
		
		// 부모 배열 초기화
		parent = new int [N+1];
		for (int i=1; i<N+1; i++) parent[i] =i;
		
		// 연결 정보 입력
		for(int i=1; i<N+1; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j=1; j<N+1; j++) {
				int sel = Integer.parseInt(st.nextToken());
				if (sel == 1) union(i, j);
			}
		}
		
		// 여행 계획 입력
		st = new StringTokenizer(bf.readLine());
		int start = Integer.parseInt(st.nextToken()); // 시작점
		boolean flag = true;
		for (int i=1; i<M; i++) {
			int p = Integer.parseInt(st.nextToken()); 
			if (find(start) == find(p)) continue;
			flag = false; // 부모가 같지 않으면 여행 불가능
		}
		
		// 출력
		if (flag == true) System.out.println("YES");
		else System.out.println("NO");
	}

}

1. ArrayList 사용

이 경우에는 같은 여행지에 두 번 연속 들릴 경우 오답이 나오기 때문에 예외 처리를 해주어야 한다.

💡 input

3 2 0 0 0 0 0 1 0 1 0 1 1

wrong output

NO

ans

YES

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static ArrayList <Integer> link[];
	static boolean [] isVisited;
	
	// start, end 두 지역이 이어져있는지 확인
	static boolean BFS(int start, int end) {
		Queue <Integer> que = new ArrayDeque();
		
		que.add(start);
		
		isVisited = new boolean[N+1];
		isVisited[start] = true;
		
		while(!que.isEmpty()) {
			int now = que.poll();
			for (int next : link[now]) {
				if (next == end) return true;
				if (isVisited[next]) continue;
				isVisited[next] = true;
				que.add(next);
			}
		}
		
		return false;
	}
	
	public static void main(String [] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(bf.readLine());
		
		link = new ArrayList[N+1];
		for (int i=1; i<N+1; i++) link[i] = new ArrayList();
		
		// 연결 정보 입력
		for(int i=1; i<N+1; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j=1; j<N+1; j++) {
				int sel = Integer.parseInt(st.nextToken());
				if (sel == 1) {
					link[i].add(j);
					link[j].add(i);
				}
			}
		}
		
		// 여행 계획 입력
		st = new StringTokenizer(bf.readLine());
		
		boolean flag = true; // 가능 여부
		int start = Integer.parseInt(st.nextToken()); // 시작점
		for (int i=1; i<M; i++) {
			int end = Integer.parseInt(st.nextToken()); // 도착점
			
			**if(start == end) continue; // 시작점과 도착점이 같은 경우 무조건 가능**
			
			if (!BFS(start, end)) { // 갈 수 없다면 종료
				flag = false;
				break;
			}
			start = end;
		}
		
		// 출력
		if (flag) System.out.println("YES");
		else System.out.println("NO");
	}
}