|
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
|
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
int[][] distance = new int[n + 1][n + 1];
int MAX_VALUE = 101;
// distance 초기화
for (int[] arr : distance) {
Arrays.fill(arr, MAX_VALUE);
}
for (int[] arr : results) {
distance[arr[0]][arr[1]] = 1;
}
// 각 위치에서 최단 경로 갱신
for (int k = 0; k < n + 1; k++) {
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (distance[i][j] > distance[i][k] + distance[k][j])
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
for (int i = 1; i < distance.length; i++) {
boolean flag = true;
for (int j = 1; j < distance[i].length; j++) {
// 자기 자신일 때 제외
if (i == j)
continue;
// 양쪽 다 길이 막힌 경우, 순위를 매길 수 없음
if (distance[i][j] == MAX_VALUE && distance[j][i] == MAX_VALUE) {
flag = false;
break;
}
}
if (flag)
answer++;
}
return answer;
}
}
|
cs |
먼저 어떻게 순위를 확실하게 매길 수 있는지를 알아야 한다.
그 방법은 다른 모든 정점과 연결점이 있어야 한다.
각 정점에서의 최단 경로를 구하기 위해 플로이드 워셜 알고리즘을 이용하였다.
이 최단 경로를 통해, 연결점이 없는 정점의 경우 순위를 매길 수 없다고 판단하였다.
인접 리스트를 통해 정점에 대한 경로를 탐색하는 코드를 짰지만, 시간 초과가 나서 문제를 해결하지는 못하였다.
그 코드는 아래와 같다.
|
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import java.util.*;
public class test {
private static ArrayList<ArrayList<Integer>> parents = new ArrayList<ArrayList<Integer>>();
private static ArrayList<ArrayList<Integer>> childrens = new ArrayList<ArrayList<Integer>>();
// 그래프 추가
public static void put(int x, int y) {
parents.get(y).add(x);
childrens.get(x).add(y);
}
public static void getAllParents(ArrayList<Integer> parent, HashSet<Integer> parentSet) {
if (parent.size() == 0)
return;
for (int i = 0; i < parent.size(); i++) {
parentSet.add(parent.get(i));
getAllParents(parents.get(parent.get(i)), parentSet);
}
}
public static void getAllChildrens(ArrayList<Integer> children, HashSet<Integer> childrenSet) {
if (children.size() == 0)
return;
for (int i = 0; i < children.size(); i++) {
childrenSet.add(children.get(i));
getAllChildrens(childrens.get(children.get(i)), childrenSet);
}
}
// 그래프 출력 (인접리스트)
public static void printGraphToAdjList() {
System.out.println("부모 그래프 ");
for (int i = 1; i < parents.size(); i++) {
System.out.print("정점 " + i + "의 인접리스트");
for (int j = 0; j < parents.get(i).size(); j++) {
System.out.print(" -> " + parents.get(i).get(j));
}
System.out.println();
}
System.out.println();
System.out.println("자식 그래프");
for (int i = 1; i < childrens.size(); i++) {
System.out.print("정점 " + i + "의 인접리스트");
for (int j = 0; j < childrens.get(i).size(); j++) {
System.out.print(" -> " + childrens.get(i).get(j));
}
System.out.println();
}
}
public static void main(String[] args) {
int n = 5;
int[][] results = { { 4, 3 }, { 4, 2 }, { 3, 2 }, { 1, 2 }, { 2, 5 } };
int answer = 0;
// 인접 리스트 생성
for (int i = 0; i < n + 1; i++) {
parents.add(new ArrayList<Integer>());
childrens.add(new ArrayList<Integer>());
}
// 인접 리스트 초기화
for (int i = 0; i < results.length; i++) {
put(results[i][0], results[i][1]);
}
for (int i = 1; i <= n; i++) {
HashSet<Integer> parentSet = new HashSet<Integer>();
HashSet<Integer> childrenSet = new HashSet<Integer>();
// 모든 부모, 자식을 set에 저장
getAllParents(parents.get(i), parentSet);
int parentNum = parentSet.size();
getAllChildrens(childrens.get(i), childrenSet);
int childrenNum = childrenSet.size();
// 순위를 확정낼 수 있을 경우
if (parentNum + childrenNum == n - 1)
answer++;
}
System.out.println(answer);
}
}
|
cs |
참고 사이트 : https://tosuccess.tistory.com/47, https://simsimjae.tistory.com/146