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]);
}
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.