[BOJ] 백준 10159번 저울 (Java)

#10159 저울

난이도 : 골드 3

유형 : 그래프/ 플로이드-와샬

10159번: 저울

▸ 문제

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)

[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다. 

비교 결과가 모순되는 입력은 없다고 가정한다. 위 예제의 기존 측정 결과에 [3]>[1]이 추가되었다고 가정하자. 이 경우 [1]>[2], [2]>[3]이므로 우리는 [1]>[3]이라는 것을 예측할 수 있는데, 이는 기존에 측정된 결과 [3]>[1]과 서로 모순이므로 이러한 입력은 가능하지 않다. 

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하는 프로그램을 작성하시오. 

 

▸ 입력

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

 

▸ 출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

 

 

 

 

문제 풀이 🖋 

처음 풀이 설계는 위상정렬과 dfs탐색을 사용하여 해결하려고 했다. 그런데 시간초과를 당해버렸다. 

 

 

위상 순서를 메긴 다음에 루트 노드들을 뽑아서 DFS탐색을 통해 해당 루트 노드로 저울을 잴 수 있는 집합을 구하였다.

문제의 예시를 예로들면 루트 노드는 1과 6으로 나와서 DFS탐색을 통해 (1-2-3-4), (6-5-4)을 구하였는데 아마 DFS에서 시간 초과를 당한 것 같다. 

* 최악의 경우 조합(dfs코드)은 nCr에서 r의 크기가 커질수록 시간복잡도가 기하급수적으로 올라가기 떄문에 n값이 20이상 넘어가면 위험하다고 한다.

- 조합 시간 복잡도 O(n!)

 

↓ 실패 코드

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static int[] res;
	static List<Integer>[] list;
	static boolean[] check, dCheck;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int[] ranks = new int[n+1];
		res = new int[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
			res[i] = n;
		}
		
		for(int i=0; i<m; i++) {
			 st = new StringTokenizer(br.readLine());
			 int a1 = Integer.parseInt(st.nextToken());
			 int a2 = Integer.parseInt(st.nextToken());
			 
			 list[a1].add(a2);
			 ranks[a2] += ranks[a1]+1;
		}
		
		dCheck= new boolean[n+1];
		for(int i=1; i<n+1; i++) {
			if(ranks[i] ==0) {
				check = new boolean[n+1];
				check[i] = true;
				dfs(i,1);
				check[i] = false;
			}
		}
        
		for(int i=1; i<n+1; i++) {
			System.out.println(res[i]);
		}
		System.out.println(sb.toString());
	}
	
	static void dfs(int pos, int cnt) {
		
		if(list[pos].size() ==0) {
			for(int i=1; i<n+1; i++) {
				if(check[i]) {
					if(dCheck[i]) {
						res[i]++;
					}
					res[i] -= cnt;
					dCheck[i]  = true;
				}
			}
			return;
		}
		
		for(int next :list[pos]) {
			check[next] = true;
			dfs(next, cnt+1);
			check[next] = false;
		}
	}
}

 

그래서 문제 힌트를 보니 플로이드 와샬이 적혀있었다. 이 문제에 최단경로를 구하는 그래프를 어떻게 활용하지? 생각하면서 지문을 다시 읽어보니 감이 와버렸다.

 

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 

 

📚 조건

1. 물건의 개수(정점) N ( 5 <= N <= 100)
2. 물건 쌍의 개수(간선) M ( 0 <= M <= 2,000)
3. 그래프에 싸이클은 존재하지 않는다. (1>3, 3>1 모순. 입력값 x)
4. a1 > a2, a2> a3 이면 a1 > a3임을 알 수 있다.

 

풀이 순서는 1) 정점과 주어지는 간선을 입력한 후 2) 해당 데이터를 통해 비교가 가능한 정점을 모두 찾아 값을 넣어주면 된다.

 

1번 로직

정점과 정점사이의 value를 1, -1로 설정하자.

• a1 > a2 일 때는 arr[a1][a2] = 1;
• a1 < a2 일 때는 arr[a2][a1] = -1;

 

2번 로직

이제 값이 입력된 인접배열을 가지고 플로이드-와샬 알고리즘을 통해 각 물건간의 비교가 가능한지 측정해보자.

 

a1 > a2은  arr[a1][a2] =1 이고

a2 > a3은  arr[a2][a3]=1 이므로

 →  arr[a1][a3] = 1이 된다.

 

반대로도 마찬가지이다.

a1 < a2은  arr[a2][a1] = -1 이고

a2 < a3은  arr[a3][a2]= -1 이므로

 →  arr[a3][a1] = -1이 된다.

 

 

코드로 나타내면 다음과 같다.

// 2번 로직
for(int k=1; k<n+1; k++) {
	for(int i=1; i<n+1; i++) {
		for(int j=1; j<n+1; j++) {
			if(arr[i][k] == 1 && arr[k][j] ==1) {
				arr[i][j] =1;
			}
			
			if(arr[i][k] == -1 && arr[k][j] == -1) {
				arr[i][j] = -1;
			}
		}
	}
}

 

 

최종 풀이 코드 ✔︎ 

플로이드 알고리즘의 핵심 개념은 i,j의 정점 사이를 거쳐가는 지점을 모두 조회하여 최단 경로를 찾는것이다.

 

arr[i][j] > arr[i][k] + arr[k][j] 

 

→ 이 문제에서는 개념을 모든 정점에서 모든 정점의 최단경로를 구하는 것이 아닌 모든 정점에 대한 관계를 조회하도록 만들었다는게 정말 좋은 개념 활용방법을 제시한 것 같다.

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		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+1; i++) {
			arr[i][i] = 1;
		}
		for(int i=0; i<m; i++) {
			 st = new StringTokenizer(br.readLine());
			 int a1 = Integer.parseInt(st.nextToken());
			 int a2 = Integer.parseInt(st.nextToken());
			 
			 arr[a1][a2]=1; // a1 > a2;
			 arr[a2][a1]= -1; // a2 > a1;
		}
		
		for(int k=1; k<n+1; k++) {
			for(int i=1; i<n+1; i++) {
				for(int j=1; j<n+1; j++) {
					if(arr[i][k] == 1 && arr[k][j] ==1) {
						arr[i][j] =1;
					}
					
					if(arr[i][k] == -1 && arr[k][j] == -1) {
						arr[i][j] = -1;
					}
				}
			}
		}
		
		for(int i=1; i<n+1; i++) {
			int cnt=0;
			for(int j=1; j<n+1; j++) {
				if(arr[i][j] != 0) {
					cnt++;
				}
			}
			sb.append((n-cnt)+"\n");
			
		}
		System.out.println(sb.toString());
	}
}