Study/Baekjoon

[Java] Baekjoon1976: 여행 가자

devyoseph 2022. 2. 24. 00:04

여행 가자

2 초 128 MB 19988 7720 5718 37.837%

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

풀이

연결관계만 알아보는 방법에는 크게 두가지가 있습니다.

DFS를 통해 재귀호출을 통한 방문체크 방식, 유니온 파인드를 이용한 합집합 방식

입력값이 많으므로 유니온 파인드 방식을 이용해 구현했습니다.

 

유니온 파인드 구현

1. find() 메소드 + union() 메서드

static int[] parents;

static int find(int a) { // 현재 집합의 대표값을 구해주는 메소드
    if(parents[a]==a) return a;

    parents[a] = find(parents[a]); //경로 압축 기능
    
    return parents[a]; //부모를 재귀적으로 호출
}

static void union(int a, int b) { // 두 집합을 합치는 메소드
    int aRoot = find(a); //원소 a가 속한 집합의 대표를 찾아서 저장
    int bRoot = find(b); //원소 b가 속한 집합의 대표를 찾아서 저장

    parents[aRoot] = bRoot; // 대표값의 부모만 변경
}

거의 암기 수준입니다. 유니온 파인드 구현에 필수인 두 메서드입니다.

2. 초기 집합 : 자기 자신이 대표인 각각의 집합 생성

유니온 파인드의 목적은 서로소인 집합을 빠르게 합치는 것입니다.

모든 원소를 먼저 집합의 개념으로 만들어주어야 하며 집합의 대표값을 생성해주면 곧 자기 자신이 대표인 집합이됩니다.

parents = new int[N]; // 원소 N개 존재

for(int i=1; i<N; i++) {
   parents[i] = i; // 자기 자신이 곧 대표 = 원소가 1개인 집합들 생성 
}

 

 

합치기

연결관계가 주어집니다.

0 1 0   // 0번 도시는 1번 도시와 연결
1 0 1	// 1번 도시는 0번 도시와 연결, 1번 도시는 2번 도시와 연결
0 1 0	// 2번 도시는 1번 도시와 연결

위와 같은 경우 연결관계를 주석과 같습니다.

union 메서드를 이용해 모조리 합쳐줍니다.

for (int i = 0; i < N; i++) {
   st = new StringTokenizer(br.readLine()); // 입력값을 라인마다 받아주고
   
   for (int j = 0; j < N; j++) {
       if(st.nextToken().equals("1")) { // 1, 즉 연결되어있으면
           union(i,j); // 두 원소가 포함된 집합을 서로 합쳐줌
       }
   }
   
}

 

결과 구하기

모든 도시를 방문하기 위해선 도시가 서로 연결되어있다는 뜻입니다.

이 말을 집합으로 가져오면 같은 집합 안에 포함된 도시라는 뜻입니다.

즉 각 원소가 가리키는 대표값이 같습니다.

제시된 도시 중 첫번째 도시의 대표값을 추출한 다음 이 대표값과 다른 도시의 대표값이 모두 같은지 확인합니다.

boolean judge = true; // 같은 도시인지 판별하는 불린 변수

st = new StringTokenizer(br.readLine());

int root = find(Integer.parseInt(st.nextToken())-1); // 제시된 처음 도시 대표값 추출

while(M-->1) {
   if(root!=find(Integer.parseInt(st.nextToken())-1)) { // 그 뒤의 도시들도 같은 대표인지 확인
       judge = false; // 다르다면? 서로 같은 집합이 아니므로 false
       break;
   }
}
System.out.println(judge?"YES":"NO");

 

전체코드

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

public class Main {
	static int[] parents;
	
	static int find(int a) {
		if(parents[a]==a) return a;
		
		parents[a] = find(parents[a]);
		return parents[a];
	}
	
	static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		parents[aRoot] = bRoot;
	}
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer st;
	   int N = Integer.parseInt(br.readLine());
	   parents = new int[N];
	   for(int i=1; i<N; i++) {
		   parents[i] = i;
	   }
	   int M = Integer.parseInt(br.readLine());
	   
	   for (int i = 0; i < N; i++) {
		   st = new StringTokenizer(br.readLine());
		   for (int j = 0; j < N; j++) {
			   if(st.nextToken().equals("1")) {
				   union(i,j);
			   }
		   }
	   }
	   
	   boolean judge = true;
	   
	   st = new StringTokenizer(br.readLine());
	   
	   int root = find(Integer.parseInt(st.nextToken())-1);
	   
	   while(M-->1) {
		   if(root!=find(Integer.parseInt(st.nextToken())-1)) {
			   judge = false;
			   break;
		   }
	   }
	   System.out.println(judge?"YES":"NO");
	}   
}

저작자표시