반응형
DFS를 이용하여 푸는 문제이다.
유향 그래프이기때문에 하나의 정점을 기준으로 1.정방향 DFS, 2.역뱡항 DFS 둘다를 거쳤을 때 모든 정점을 방문한형태를 나타낸다면 자신의 위치를 알고있는 정점으로 간주할수 있게되는 성질을 이용하여 풀었다.
|
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
|
package boj2;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main_bj_2458_키순서 {
static int N;
static List<Integer>[] graph;
static List<Integer>[] reverseGraph;
static boolean[] visit;
static int result;
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
graph=new ArrayList[N+1];
for(int i=0;i<=N;i++)
graph[i]=new ArrayList<>();
reverseGraph=new ArrayList[N+1];
for(int i=0;i<=N;i++)
reverseGraph[i]=new ArrayList<>();
int M=Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st=new StringTokenizer(br.readLine());
int u=Integer.parseInt(st.nextToken());
int v=Integer.parseInt(st.nextToken());
graph[u].add(v);
reverseGraph[v].add(u);
}
result=0;
func();
System.out.println(result);
}
static void func() {
for(int i=1;i<=N;i++) {
visit=new boolean[N+1];
dfs(i);
reverseDfs(i);
boolean possible=true;
for(int j=1;j<=N;j++) {
if(visit[j]==false) { //하나라도 방문안한점이 있으면 fail
possible=false;
break;
}
}
if(possible==true)
result+=1;
}
}
static void dfs(int cur) {
visit[cur]=true;
for(int next:graph[cur]) {
if(visit[next]==false) {
dfs(next);
}
}
}
static void reverseDfs(int cur) {
visit[cur]=true;
for(int next:reverseGraph[cur]) {
if(visit[next]==false) {
reverseDfs(next);
}
}
}
}
|
거리를 구하는 알고리즘인 플로이드와샬로도 다음과 같이 풀이할 수 있다.
|
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
|
package boj2;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main_bj_2458_키순서_2 {
static int N;
static int[][] map;
static int INF=987654321;
static int result;
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
map=new int[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++)
map[i][j]=INF;
}
int M=Integer.parseInt(st.nextToken());
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;
map[u][v] = 1;
}
for(int k=0;k<N;k++) {
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(map[i][j]>map[i][k]+map[k][j]) {
map[i][j]=1;
}
}
}
}
result=0;
for(int i=0; i<N; i++) {
int count = 0;
for(int j=0; j<N; j++) {
if(map[i][j]==1 || map[j][i]==1)
count+=1;
}
if(count==N-1)
result++;
}
System.out.println(result);
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 11404. 플로이드 (0) | 2020.05.15 |
|---|---|
| [BOJ] 15683. 감시 (0) | 2020.05.15 |
| [BOJ] 1194. 달이 차오른다, 가자. (0) | 2020.05.14 |
| [Programmers] 비밀지도 (0) | 2020.05.14 |
| [BOJ] 2252. 줄 세우기 (0) | 2020.05.13 |