https://www.acmicpc.net/problem/1976
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
🌿 - 문제 설명
📌- 풀이
플로이드 워셜로 전체 그래프에서 갈 수 있는 곳을 전부 map에 기록을 하고 시작 지점에서 각각 지점까지 전부 갈 수 있다면 YES, 한 곳이라도 못간다면 NO를 출력하는 방식으로 풀었다.
플로이드 워셜로만 풀었는데 다른 풀이들을 찾다보니 Union_Find로 문제를 푸는 방식들이 많아서 그것들을 참고해서 다시 풀어봤다.
유니온 파인드에 대한 설명은 여기 블로그에 자세하게 설명되어 있다.
유니온 파인드 (Union Find) - Java
유니온 파인드란? 유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연속적으로 연결하여 하나의 집합으로 묶는 union 연산과 특정 노드의 루트 노드를 찾는 find 연산으로 이루어진 알고리
rachel0115.tistory.com
유니온 파인드는 일단 각 노드들을 비교해서 연결되어 있으면 가장 작은 값을 부모로 설정하도록 만들면 되는데 여기서는 경로를 입력받을 때 1이면 i와 j가 연결되어 있으므로 parent배열을 초기화 시켜 주면서 각각 노드들의 parent를 정의해주면 된다.
그렇게 일단 모든 노드들의 parent 배열을 완성한다.
그리고 여행계획 도시들의 parent가 시작지점이라면 모든 도시를 여행할 수 있기 때문에 YES를 출력하고 시작지점과 여행 계획 도시들의 parent가 다르다면 NO를 출력하면 된다.
🔥 - Java 전체 코드(플로이드)
package 그래프.G4_1976_여행가자;
import java.io.*;
import java.util.*;
public class Main {
public static int N,M;
public static int[][] map;
public static String result="YES";
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i =0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j =0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
if(i == j){
map[i][j] = 1;
}
}
}
st = new StringTokenizer(br.readLine());
Queue<Integer> que = new LinkedList<>();
while(st.hasMoreTokens()){
que.add(Integer.parseInt(st.nextToken()));
}
int[] arr = new int[que.size()];
for(int k =0;k<N;k++){
for(int i=0;i<N;i++){
for(int j =0;j<N;j++){
if(map[i][k] == 1 && map[k][j] == 1){
map[i][j] = 1;
}
}
}
}
int num = que.size();
int count = 0;
int start = 0;
while(!que.isEmpty()){
arr[count] = que.poll()-1;
if(count ==0) start = arr[count];
count++;
}
for(int i =1;i<num;i++){
if(map[start][arr[i]] == 0){
result="NO";
}
}
System.out.println(result);
}
}
중간에 문제를 잘못읽어서 여행계획을 큐로 입력받는 곳이 있는데 이렇게 해도 문제가 풀리기도 하고, 실수를 이렇게 남겨 놓아서 나중에 다시 봤을 때 반성하기 위해서 남겨 놓았다.
🔥 - Java 전체 코드(유니온 파인드)
package 그래프.G4_1976_여행가자;
import java.io.*;
import java.util.*;
public class Main2 {
public static int N,M;
public static int[] parent;
static String result = "YES";
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
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 number = Integer.parseInt(st.nextToken());
if(number == 1){
union(i,j);
}
}
}
st = new StringTokenizer(br.readLine());
int start = find(Integer.parseInt(st.nextToken())-1);
for(int i=1;i<M;i++){
int num = Integer.parseInt(st.nextToken());
if(start != find(num-1)){
result = "NO";
break;
}
}
System.out.println(result);
}
public static int find(int x){
if(x == parent[x]){
return x;
}
return parent[x] = find(parent[x]);
}
public static void union(int x, int y){
x = find(x);
y = find(y);
if(x != y) {
if(x < y){
parent[y] = x;
}else{
parent[x] = y;
}
}
}
}