https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 제가 전에 포스팅했던 DFS https://bgspro.tistory.com/14?category=981927, BFS https://bgspro.tistory.com/15?category=981927를 정확하게 숙지 및 암기하고 있다면 실버 2 티어와 정답률 33프로의 문제임에도 불구하고 굉장히 쉽게 해결할 수 있는 문제입니다. 먼저 문제를 보겠습니다. 문제에서 그래프가 주어지고 이를 DFS로 탐색하는 경우 그리고 BFS로 탐색하는 경우를 출력하면 정답 판정을 받을 수 있습니다.
dfs와 bfs는 위의 링크를 각각 참고하면 되겠습니다.
문제 해결을 위한 팁
문제를 보면 노드들이 양방향으로 연결이 되어있는것을 알 수 있습니다. 따라서 각각의 그래프를 연결할 때 양방향으로 연결을 해야 합니다. 또한 노드가 여러 노드와 연결이 되어있다면 그중 번호가 낮은 것을 우선하여 탐색하므로 입력을 해 준 뒤 각각의 행에 오름차순으로 정렬을 해줘야 합니다.
소스코드
|
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
|
from collections import deque
n, m, v = map(int, input().split())
graph = [[] for _ in range(1+n)]
visited = [0] * (1+n)
for i in range(m):
a, b = map(int, input().split())
# 양방향 연결
graph[a].append(b)
graph[b].append(a)
for i in range(n+1):
graph[i].sort() # 연결된 노드가 여러곳일 경우 낮은 숫자를 가진 노드부터 탐색하기 위해 오름차순으로
def dfs(graph, visited, v):
print(v, end=" ")
visited[v] = 1
for i in graph[v]:
if not visited[i]:
dfs(graph, visited, i)
def bfs(graph, visited, start):
q = deque()
q.append(start)
visited[start] = 1
while q:
v = q.popleft()
print(v, end= " ")
for i in graph[v]:
if not visited[i]:
q.append(i)
visited[i] = 1
dfs(graph, visited, v)
visited = [0] * (1+n)
print()
bfs(graph, visited, v)
|
cs |
소스코드 - c++
|
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
|
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
vector<int> graph[MAX];
bool visited[MAX]; // false 초기화
bool visited2[MAX];
void dfs(int x) {
visited[x] = true;
printf("%d ", x);
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) {
dfs(y);
}
}
}
void bfs(int start) {
queue<int> q;
q.push(start);
visited2[start] = true;
while (!q.empty()) {
int x = q.front();
printf("%d ", x);
q.pop();
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited2[y]) {
q.push(y);
visited2[y] = true;
}
}
}
}
int main(void) {
int n, m, v;
scanf("%d %d %d", &n, &m, &v);
for (int i = 1; i < m + 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i < n + 1; i++) { // 정렬
sort(graph[i].begin(), graph[i].end());
}
dfs(v);
printf("\n");
bfs(v);
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2667: 단지번호붙이기 (Python) (0) | 2021.01.25 |
|---|---|
| 백준 알고리즘 2178: 미로 탐색 (Python) (0) | 2021.01.19 |
| 백준 알고리즘 2810: 컵홀더 (Python) (0) | 2021.01.19 |
| 백준 알고리즘 13305: 주유소(Python) (0) | 2021.01.19 |
| 백준 알고리즘 1715: 카드 정렬하기 (Python) (0) | 2021.01.11 |