10159번 - 저울
문제 풀이 시간 : 30분
문제 설명 :
- •
무게가 서로 다른 N개의 물건이 있다.
- •
일부 물건 쌍에 대한 저울의 결과를 가지고 있다.
- •
각 물건에 대해 그 물건과 비교 결과 알 수 없는 물건의 개수 출력
문제 풀이 :
백준을 대략 한달만에 푸는거라 재활 훈련 차 조금 쉬운 문제를 가져왔다.
처음에는 Union-Find로 풀어야하나?
하고 생각했지만 아닌 것 같아서
다른 방법을 생각하다가 생각난 것이 BFS이다.
사실 DFS가 더 맞는 것 같은데 나는 BFS로 풀었다.
내가 접근한 방식은
각 물건에 대해 자기보다 가벼운 물건을 저장한 배열을 가지고
해당 배열을 이용해 계산하는 것이다.
예를 들자면,
1 2
2 3
3 4
라는 입력이 있다면
각 배열에
1 - 2
2 - 3
3 - 4
와 같은 형식으로 저장되고,
1을 조회하면 BFS를 통해 2→3→4 로 이동하며 visited에 방문처리를 하는 것이다.
그리고 마지막에 visited배열을 보며 방문 처리가 되지 않은 물건의 개수를 세면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static ArrayList<Integer>[] arr;
public static int find(int a) {
Queue<Integer> q = new LinkedList<>();
q.add(a);
boolean[] visited = new boolean[n];
while (!q.isEmpty()) {
int temp = q.poll();
if (visited[temp-1]) {
continue;
}
visited[temp-1] = true;
q.addAll(arr[temp-1]);
}
int result = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
result++;
}
}
return result;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
arr = new ArrayList[n];
for (int i = 0; i < n; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a-1].add(b);
}
for (int i = 0; i < n; i++) {
System.out.println(find(i + 1));
}
}
}
근데 이 방식의 문제점은?
위의 예시에서 봤듯이
1 - 2
2 - 3
3 - 4
과 같이 배열이 형성되었다면,
1은 모든 경우를 제대로 찾아내지만
2는 1을 방문하지 못해서 모든 경우를 찾아내지 못한다.
그래서 나는 배열을 하나 더 만들었다.
현재의 arr 배열은 자신보다 가벼운 물건을 저장하지만
새로운 배열은 자신보다 무거운 물건을 저장하는 것이다.
즉, 위의 예시로 다시 보면
1 -
2 - 1
3 - 2
4 - 3
이렇게 저장이 되는 것이다.
그래서 bfs를 두 배열을 모두 돌려주면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static ArrayList<Integer>[] arr;
public static ArrayList<Integer>[] arr2;
public static int find(int a) {
Queue<Integer> q = new LinkedList<>();
q.add(a);
boolean[] visited = new boolean[n];
while (!q.isEmpty()) {
int temp = q.poll();
if (visited[temp-1]) {
continue;
}
visited[temp-1] = true;
q.addAll(arr[temp-1]);
}
q.addAll(arr2[a - 1]);
while (!q.isEmpty()) {
int temp = q.poll();
if (visited[temp-1]) {
continue;
}
visited[temp-1] = true;
q.addAll(arr2[temp-1]);
}
int result = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
result++;
}
}
return result;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
arr = new ArrayList[n];
for (int i = 0; i < n; i++) {
arr[i] = new ArrayList<>();
}
arr2 = new ArrayList[n];
for (int i = 0; i < n; i++) {
arr2[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a-1].add(b);
arr2[b - 1].add(a);
}
for (int i = 0; i < n; i++) {
System.out.println(find(i + 1));
}
}
}
이렇게 풀면 통과할 수 있다.
근데 이 방법은 내가 봐도 좀 이상한 것 같아서 다른 사람들의 풀이를 찾아봤다.
다른 풀이
dfs를 이용한 풀이이다.
방문 가능 개수 배열 cnt가 존재하고,
각 물건이 자신보다 가벼운 물건을 탐색한다.
각 가벼운 물건에 방문할 때마다
cnt[시작물건]++
cnt[가벼운물건]++
을 해주는 것이다.
그림으로 예를 들어보자면
초기 상태는 위와 같다.
여기서 먼저 1을 기준으로 탐색하면
다음은 2
이런식으로 5,6까지 진행한다면
아래와 같은 결과가 나온다.
그럼 우리는 이 결과를 각각 6에서 빼주면 우리가 원하는 결과를 쉽게 얻을 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static ArrayList<Integer>[] arr;
public static boolean[] visited;
public static int[] cnt;
public static void find(int start, int now) {
cnt[now]++;
for (int next : arr[now]) {
if (visited[next-1]) {
continue;
}
visited[next-1] = true;
cnt[start]++;
find(start, next-1);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
cnt = new int[n];
arr = new ArrayList[n];
for (int i = 0; i < n; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a-1].add(b);
}
for (int i = 0; i < n; i++) {
visited = new boolean[n];
visited[i] = true;
find(i, i);
}
for (int i = 0; i < n; i++) {
System.out.println(n - cnt[i]);
}
}
}