[백준] Gold IV. 여행 가자
https://www.acmicpc.net/problem/1976
사용 알고리즘
- DFS
- 유니온 파인드
풀이
DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
/*
1. 여행 계획 처음부터 BFS를 돌리면서 체크
*/
static int n, m;
static List<List<Integer>> graph = new ArrayList<>();
static boolean [] visited = new boolean[202];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
for(int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for(int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
int k = Integer.parseInt(st.nextToken());
if (k == 1) graph.get(i).add(j);
}
}
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> paths = new ArrayList<>();
for(int i = 0; i < m; i++) {
int start = Integer.parseInt(st.nextToken());
paths.add(start);
}
for(int i = 0; i < paths.size() - 1; i++) {
visited = new boolean[202];
//System.out.println(paths.get(i) + " " + paths.get(i + 1));
if (!dfs(paths.get(i), paths.get(i+1))) { // dfs를 돌리면서 다음 지점에 도달할 수 있는지 확인한다.
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
public static boolean dfs(int start, int destination) {
if (start == destination) {
return true;
}
visited[start] = true;
for(int nxt : graph.get(start)) {
if(!visited[nxt] && dfs(nxt, destination)) {
return true;
}
}
return false;
}
}
유니온 파인드
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;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
parent = new int[n + 1];
for(int i = 1; i <= n; i++) {
parent[i] = i;
}
for(int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
int k = Integer.parseInt(st.nextToken());
if (k == 1) { //
union(i, j);
}
}
}
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
for(int i = 1; i < m; i++) {
int next = Integer.parseInt(st.nextToken());
if (find(start) != find(next)) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
public static void union(int i, int j) {
i = find(i);
j = find(j);
if (i != j) {
parent[j] = i;
}
}
public static int find(int num) {
if (num == parent[num]) {
return num;
}
return parent[num] = find(parent[num]);
}
}
회고
먼저 DFS의 풀이로 접근했던 방식을 얘기해보자면, 여행 계획의 경로가 주어질 때 현재 위치에서 다음 위치로 이동할 수 있는지 여부를 찾는게 중요하다고 생각해서 DFS를 사용했다.
기존에 풀었던 방식은,
if (start == destination) {
cnt++;
return true;
}
visited[start] = true;
다음 위치에 도달했을 때 cnt를 1 증가시켜주고 dfs를 다 돌았을 때의 cnt가 m-1이라면 "YES"를 출력하고, 아니라면 "NO"를 출력하게 했는데 틀렸다는 결과가 나왔다.
반례)
4
3
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
1 2 4
위 그림인 경우 디버깅을 해봤을 떄,
start: 2 cnt: 1
start: 2 cnt: 2
start: 4 cnt: 3
start: 4 cnt: 4
한 정점에서 cnt를 두번 계산해버려서 틀린 cnt가 계산이 된다.
중복 계산을 방지하기 위해, start == destination을 체크하기 전에 방문 체크를 하면 결과가 통과한다.
visited[start] = true;
if (start == destination) {
cnt++;
System.out.println("start: " + start + " cnt: " + cnt + " destination: " + destination);
return;
}
경로 체크를 하고 방문체크를 하면 -> 중복이 발생
방문 체크를 하고 경로 체크를 하는 경우엔 중복이 발생하지 않는다.
나는 이부분이 헷갈려서 boolean으로 풀이를 했지만, 방문 처리를 어느 시점에서 하는지에 따라 결과값이 달라지는것을 확인할 수 있었다..!
Union Find를 사용한 풀이
유니온파인드를 사용해야하는 근거가 뭐가 될까?
앞서 공부했듯이, 유니온 파인드는 두 노드가 같은 집합에 속하는지 판단하기 위해서 사용된다. 위 문제에선 도시가 같은 집합에 속하는지 여부를 판단해야 하기 때문에 사용하기 적절하다고 생각했다.
find 메서드에선 해당 정점의 parent node가 자신과 같다면 바로 리턴해주고, 아니라면 재귀적으로 parent node를 찾아서 리턴해준다.
union 메서드에선 두개의 정점을 find 메서드에 넣은 결과값을 비교하는데, 값이 다른 경우엔 parent[j] = i와 같이 값을 재설정 해준다.