https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
1. 배열을 이용해서 푼 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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N,M,V;
static int [][] arr;
static boolean [] visit;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
V=Integer.parseInt(st.nextToken());
arr = new int[N+1][N+1];
visit = new boolean[N+1];
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a][b]=1;
arr[b][a]=1;
}
dfs(V);
sb.append("\n");
Arrays.fill(visit,false);
bfs();
System.out.println(sb);
}
public static void dfs(int v){
visit[v]=true;
sb.append(v+" ");
for(int i=1;i<arr[v].length;i++){
if(!visit[i] && arr[v][i]==1){
dfs(i);
}
}
}
|
cs |
배열을 돌면서 방문하지 않았고, 서로 연결되어있으면 dfs로 탐색을 한다.
35줄 Arrays.fill(visit,false); 는 방문 배열을 초기화하기 위한 것이다.
출력시간을 줄이기 위해 BufferedReader와 StringBuilder를 사용했다.
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N,M,V;
static ArrayList<Integer>[] arr;
static boolean [] visit;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
V=Integer.parseInt(st.nextToken());
arr = new ArrayList[N+1];
visit = new boolean[N+1];
for(int i=1;i<=N;i++){
//리스트 만들어 배열에 넣음
arr[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());
arr[a].add(b);
arr[b].add(a);
}
for(int i=1;i<=N;i++){
Collections.sort(arr[i]);
}
dfs(V);
sb.append("\n");
Arrays.fill(visit,false);
bfs();
System.out.println(sb);
}
public static void dfs(int v){
visit[v]=true;
sb.append(v+ " ");
for(int i=0;i<arr[v].size();i++){
int cur = arr[v].get(i);
if(!visit[cur])
dfs(cur);
}
}
public static void bfs(){
Queue<Integer> q = new LinkedList<Integer>();
q.add(V);
while(!q.isEmpty()){
int cur = q.poll();
visit[cur]=true;
sb.append(cur+ " ");
for(int i=0;i<arr[cur].size();i++){
int nxt = arr[cur].get(i);
if(!visit[nxt]){
q.add(nxt);
visit[nxt]=true;
}
}
}
}
}
|
cs |
인접리스트 방식으로 풀면 배열에선 진행하지 않았던 작업을 더 해줘야하는데,
하나는 23줄이다. 리스트를 만들어서 배열에 넣는 작업,
또 하나는 38줄 작업인데 아까는 배열을 차례로 방문하니까 정렬 작업이 필요 없었는데
이건 인접리스트 방법이라서 정렬을 한번 해주어야 한다.
그리고 bfs를 구현할때는 Queue를 이용해서 구현해준다.