ALGORITHM/BOJ
[백준] 10159 저울
0298
2021. 8. 31. 23:38
https://www.acmicpc.net/problem/10159
10159번: 저울
첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩
www.acmicpc.net
2021-08-31
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] dist;
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine().trim());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(bf.readLine().trim());
M = Integer.parseInt(st.nextToken());
dist = new int[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i == j) continue;
dist[i][j] = 987654321;
}
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
dist[a][b] = 1;
}
for(int mid = 0; mid < N; mid++) {
for(int start = 0; start < N; start++) {
for(int end = 0; end < N; end++) {
if(dist[start][end] > dist[start][mid] + dist[mid][end]) {
dist[start][end] = dist[start][mid] + dist[mid][end];
}
}
}
}
int[] ans = new int[N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i == j) continue;
if(dist[i][j] == 987654321 && dist[j][i] == 987654321) ans[i]++;
}
}
for(int i = 0; i < N; i++) {
System.out.println(ans[i]);
}
}
}
|
cs |
#문제풀이
https://void2017.tistory.com/317?category=820802
[프로그래머스] 순위
https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 2021-08-30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
void2017.tistory.com
어제 푼 이 문제 때문에 풀었다. 완전 똑같은 문제더라..