[BOJ][1260] DFS와 BFS
Updated:
1. 문제 링크
https://www.acmicpc.net/problem/1260
2. 사용 알고리즘
DFS, BFS
3. 풀이
DFS와 BFS 구현
4. 소스 코드
4-1. C++
https://github.com/dev-aiden/problem-solving/blob/main/boj/1260.cpp
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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> arr[1003];
int check[1003];
queue<int> q;
void dfs(int num) {
check[num] = 1;
cout << num << " ";
int len = arr[num].size();
for(int i = 0; i < len; ++i) {
if(!check[arr[num][i]]) dfs(arr[num][i]);
}
}
void bfs(int num) {
q.push(num);
check[num] = 1;
while(!q.empty()) {
int temp = q.front();
cout << temp << " ";
q.pop();
int len = arr[temp].size();
for(int i = 0; i < len; ++i) {
if(!check[arr[temp][i]]) {
q.push(arr[temp][i]);
check[arr[temp][i]] = 1;
}
}
}
cout << "\n";
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m, v; cin >> n >> m >> v;
for(int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
arr[a].push_back(b); arr[b].push_back(a);
}
for(int i = 1; i <= n; ++i) sort(arr[i].begin(), arr[i].end());
dfs(v);
cout << "\n";
for(int i = 0; i <= n; ++i) check[i] = 0;
bfs(v);
return 0;
}
4-2. JAVA
https://github.com/dev-aiden/problem-solving/blob/main/boj/1260.java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] arr = new ArrayList[1003];
static boolean[] check;
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());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
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]);
check = new boolean[n + 1];
dfs(v);
sb.append("\n");
check = new boolean[n + 1];
bfs(v);
System.out.println(sb);
}
public static void dfs(int num) {
check[num] = true;
sb.append(num).append(" ");
int len = arr[num].size();
for(int i = 0; i < len; ++i) {
if(!check[arr[num].get(i)]) dfs(arr[num].get(i));
}
}
public static void bfs(int num) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(num);
check[num] = true;
while(!q.isEmpty()) {
int temp = q.remove();
sb.append(temp).append(" ");
int len = arr[temp].size();
for(int i = 0; i < len; ++i) {
if(!check[arr[temp].get(i)]) {
q.add(arr[temp].get(i));
check[arr[temp].get(i)] = true;
}
}
}
sb.append("\n");
}
}
Leave a comment