문제
N개의 물건과 무게 비교 결과 M개가 주어질 때, 각 물건에 대해 무게를 비교할 수 없는 물건의 수를 구하는 문제다. A가 B보다 무겁다는 정보가 있으면 A→B 간선을 추가한다. 전이 관계(A > B이고 B > C이면 A > C)를 전부 반영해야 하므로 플로이드-워셜로 도달 가능성을 완전히 계산한다.
입력
- 첫째 줄: 물건 수 N (2 이상 100 이하)
- 둘째 줄: 비교 결과 수 M (1 이상 N*(N-1)/2 이하)
- 이후 M개 줄: A B (A가 B보다 무거움)
출력
각 물건마다 비교 불가능한 물건 수를 한 줄씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 1 2 2 3 3 4 2 4 | 0 0 0 0 |
풀이
arr[i][j](i가 j보다 무거움)와 rra[i][j](j가 i보다 무거움, 역방향) 두 행렬에 플로이드-워셜을 적용한 뒤 합쳐서 비교 가능 여부를 판별한다.
- 입력으로
arr[u][v]=true,rra[v][u]=true동시 저장 - 두 행렬 각각에 플로이드-워셜 3중 반복문 적용 → 전이적 도달 관계 완성
arr[i][j] |= rra[i][j]로 합산 —arr[i][j]가 true이면 i와 j는 비교 가능- 각 물건 i에 대해, 자신을 제외한 j 중
arr[i][j] == false인 수를 카운트
핵심 아이디어: 정방향 그래프와 역방향 그래프에 각각 플로이드-워셜을 실행하면 "크거나 작거나" 두 방향의 전이 관계를 모두 O(N^3)에 구할 수 있다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day121BOJ10159저울FloydWarshall공부 { // 10159 저울 플로이드 와샬
static int N, M;
static boolean[][] arr, rra;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
arr = new boolean[N][N];
rra = new boolean[N][N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
arr[u][v] = true;
rra[v][u] = true;
}
// 플로이드 와샬 알고리즘
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][k] && arr[k][j])
arr[i][j] = true;
if (rra[i][k] && rra[k][j])
rra[i][j] = true;
}
}
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
arr[i][j] |= rra[i][j];
for (int i = 0; i < N; i++) {
int cnt = 0;
for (int j = 0; j < N; j++) {
if (i == j)
continue;
if (!arr[i][j])
cnt++;
}
sb.append(cnt + "\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(V³)
- 공간: O(V²)