풀이 방법
모든 물건에서 비교 결과를 알 수 없는 물건의 개수를 출력해야 되기 때문에 플로이드-와셜을 사용했다.
일단 비교 결과를 저장할 테이블을 만들고 100으로 채워넣었다. (그냥 비교 할 수 없는 경우를 100 으로 사용했음)
자기 자신과 비교는 0으로 바꿔주었다.
내가 비교하는 수보다 크면 1, 작으면 -1 로 두었다.
플로이드-와셜을 사용해서 두 수를 비교할 때 중간에 낄수 있는 수가 있으면 넣어 주었다.
내 코드
package com.company;
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 = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int[][] array = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(array[i], 100);
}
for (int i = 1; i <= n; i++) {
array[i][i] = 0;
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
array[a][b] = 1;
array[b][a] = -1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(array[i][k] == 1 && array[k][j] == 1)
array[i][j] = 1;
else if(array[i][k] == -1 && array[k][j] == -1)
array[i][j] = -1;
}
}
}
for (int i = 1; i <= n; i++) {
int count = 0;
for (int j = 1; j <= n; j++) {
if(array[i][j] == 100)
count++;
}
System.out.println(count);
}
}
}
dfs 사용 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Integer>[] arr1;
static ArrayList<Integer>[] arr2;
static boolean[] visited;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
arr1 = new ArrayList[N + 1];
arr2 = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
arr1[i] = new ArrayList<>();
arr2[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr1[a].add(b);
arr2[b].add(a);
}
for (int i = 1; i <= N; i++) {
visited = new boolean[N + 1];
System.out.println(N + 1 - dfs1(i) - dfs2(i));
}
}
static int dfs1(int x) {
int value = 1;
visited[x] = true;
for (int i = 0; i < arr1[x].size(); i++) {
if (!visited[arr1[x].get(i)])
value += dfs1(arr1[x].get(i));
}
return value;
}
static int dfs2(int x) {
int value = 1;
visited[x] = true;
for (int i = 0; i < arr2[x].size(); i++) {
if (!visited[arr2[x].get(i)])
value += dfs2(arr2[x].get(i));
}
return value;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
숨바꼭질 3 -13529번 (0) | 2021.10.03 |
---|---|
DFS와 BFS - 1260번 (0) | 2021.10.02 |
백도어 - 17396번 (0) | 2021.10.01 |
최단경로 - 1753번 (0) | 2021.10.01 |
동전 2 - 2294번 (0) | 2021.09.29 |