[java] 1976 여행 가자

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

그래프 탐색을 하여 여행 계획에 속한 도시들을 방문이 가능한 지 확인하는 것이 문제의 핵심이라고 생각했다.

1. 그래프 탐색
은 풀어왔던대로 인접 행렬 int[][] 또는 인접 그래프 ArrayList<>() 를 생성한 다음
그래프 정보를 받아준 후에,
첫번째 여행도시부터 인접한 노드를 방문했다 for(int nxt : graph[start])

2. 여행 계획에 속한 도시들을 방문이 가능한 지 확인
전체 도시들 만큼 boolean 을 만들어 그래프 탐색 중 방문했다면 true 로 바꿔주고
마지막에 전체 여행 계획 도시들 중 하나라도 방문하지 않은 도시가 있다면 NO 를 출력하게 했다.

다른 풀이

유니온 파인드 를 사용하여 해결하는 방법도 있었다.
방문해야할 도시들의 부모를 확인하여 전부 같다면 YES 아니면 NO !

3. 코드

나의 풀이 ) 그래프 탐색 후 boolean 으로 확인

import java.io.*;
import java.util.*;

public class Main {

	static int N, M ; // 도시의 수, 여행 계획에 속한 도시의 수
	static ArrayList<Integer>[] graph ;
	static int[] travelCities; 
	static boolean[] visitCities; 
 
	public static void main(String[] args) throws IOException {
		// 값 입력받기 -->
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;

		N = Integer.parseInt(br.readLine()); 
		M = Integer.parseInt(br.readLine());
		graph = new ArrayList[N];
		visitCities = new boolean[N];
		travelCities = new int[M];
		for(int i=0;i<N;i++) graph[i] = new ArrayList();

		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++){
				int now = Integer.parseInt(st.nextToken()); 
				if(now == 1) graph[i].add(j);
			}
		}

		st = new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) travelCities[i] = Integer.parseInt(st.nextToken())-1; 
		// <--

		travel(travelCities[0]); // 첫번째 도시부터 여행 시작
		
        //  visitCities 값으로 방문여부 확인하기
		boolean ans = true ;
		for(int i=0;i<M;i++){
			if(!visitCities[travelCities[i]]){
				ans = false;
				break;
			}
		}
        
        // 값 출력
		System.out.println(ans ? "YES":"NO");
	}

	public static void travel(int start){ // 그래프 탐색
		visitCities[start] = true;

		for(int nxt : graph[start]){
			if(!visitCities[nxt]){
				travel(nxt) ;
			}
		}

	}
}

유니온 파인드 풀이 )

import java.io.*;
import java.util.*;

import javax.swing.text.DefaultStyledDocument.ElementSpec;

class Node{
	int x, y;
	Node(int x, int y){
		this.x = x ;
		this.y = y ;
	}
}

public class Main {

	static int N, M ; // 도시의 수, 여행 계획에 속한 도시의 수
	static int CheckParent = -1; 
	static int[] parent; 
 
	public static void main(String[] args) throws IOException {
		// 값 입력받기 -->
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;

		N = Integer.parseInt(br.readLine()); 
		M = Integer.parseInt(br.readLine());
		parent = new int[N];
		for(int i=0;i<N;i++) parent[i] = i;

		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++){
				int now = Integer.parseInt(st.nextToken()); 
				if(now == 1) union(i,j);
			}
		}
		// <--
		boolean ans = true ;

		st = new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) {
			int nowCity = Integer.parseInt(st.nextToken())-1; 
			if (CheckParent == -1 ) CheckParent = find(nowCity);
			else{
				if(CheckParent != find(nowCity)){
					System.out.println("NO");
					return;
				}
			}
		}
		System.out.println("YES");
	}

	public static void union(int x, int y){
		int xP = find(x);
		int yP = find(y);
		if(xP == yP) return;
		parent[yP] = xP ;
	}

	public static int find(int idx){
		if(parent[idx] == idx) return idx ;
		else return find(parent[idx]);
	}

}

시간

맞았습니다!! 유니온 파인드
틀렸습니다 2개 - 유니온파인드 틀림!ㅎㅎ
맞았습니다!! 첫번째 풀이