728x90
51번 여행 가자
내가 떠올린 풀이 해설
도시 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다는 아이디어를 떠올릴 수 있으면 쉽게 해결된다.
일반적으로 유니온 파인드는 그래프에서 많이 활용되지만, 위 문제와 같이 단독으로 활용할 수 있다는 점도 참고해야 된다.
인접 행렬을 탐색하면서 연결될 때마다 union연산을 수행하는 방식으로 풀어가면 된다. 도시와 여행 경로를 저장하고 각 노드와 관련된 대표 노드 배열의 값을 초기화한다. 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결돼 있을 때 union연산을 수행한다. 이때 항상 큰 도시가 대표도시가 되도록 union 연산의 매개변수를 변경한다. 마지막으로 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 출력하면 된다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1976 {
static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] arr = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int[] route = new int[m + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= m; i++) {
route[i] = Integer.parseInt(st.nextToken());
}
parent = new int[n + 1];
for(int i = 1; i <= n; i++) {
parent[i] = i;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(arr[i][j] == 1) {
union(i, j);
}
}
}
// 여행 계획 도시들이 1개의 대표 도시로 연결돼 있는지 확인하기
int index = find(route[1]);
for(int i = 2; i < route.length; i++) {
if(index != find(route[i])) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
private static void union(int i, int j) {
i = find(i);
j = find(j);
if(i != j) {
parent[j] = i;
}
}
private static int find(int j) {
if(parent[j] == j) {
return j;
}
else {
return parent[j] = find(parent[j]);
}
}
}
오늘의 회고
오늘은 union find 문제를 풀었습니다. 오늘까지 해서 복습은 마무리되었습니다. 복습으로 느낀 점은 알고리즘을 대비할 때 문제를 많이 풀려고 하지 말고 하나를 풀더라도 정확하게 이해하고 풀어야 한다고 느꼈습니다. 복습하면서 다시 푸는데 안 풀리는 문제들도 많았고 이해를 하면서 내 것으로 만드는 과정을 가지겠습니다.
728x90
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| Do it! 알고리즘 코딩 테스트 (54번 ~ 56번) (0) | 2022.06.14 |
|---|---|
| Do it! 알고리즘 코딩 테스트 (52번 ~ 53번) (0) | 2022.06.13 |
| Do it! 알고리즘 코딩 테스트 (50번) (0) | 2022.06.09 |
| Do it! 알고리즘 코딩 테스트 (49번) (0) | 2022.06.08 |
| Do it! 알고리즘 코딩 테스트 (48번) (0) | 2022.06.07 |
