https://www.acmicpc.net/problem/12600
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
___________________________________________________
입력
1.정점의 개수 N(1 ≤ N ≤ 1,000),
2.간선의 개수 M(1 ≤ M ≤ 10,000)
3.탐색 시작정점
간선은 양방향
___________________________________________________
출력
목표: 방문순서 출력하기.
단, 방문순서는 노드의 번호가 작은순서 우선으로 방문한다.
(생각해 볼수 있는것)
1.애초에 자료구조에 들어갈때 작은것이 맨위로 올라가게끔
저장하는 자료구조? priority queue BFS에는 유용하겠다.
2.아니면 일단 넣고... 각각 노드를 기준으로 각각 next노드들을
sort하는 방법?
___________________________________________________
필요한 자료구조들
벡터
그래프를 만들기 위해서
방문배열을 만들기 위해서
큐
BFS를 만들기 위해서.
___________________________________________________
for문의 다양한 사용법
1.for(int nxt :G[node] )
2.이터레이터
___________________________________________________
생각방법.
A.그래프 만들기
양방향 간선이므로
1->2 있으면 2->1도 있어야한다.
사실.. 정대각 행렬들을 기준으로 선대칭이다.
B.탐색방법 설계
___________________________________________
ⓐDFS는 재귀적인 탐색을하면된다.
#재귀 : 탐색
#for : next 주변 노드 고르기
#is visit? : yes or no
1.DFS(시작정점);
2.시작정점은 방문되었다.
visit[cur_node] = true;
3.다음노드를 살펴보자.
_
| for문을 사용할것이다.
| {
| G[node] 의 자식노드를 살펴본다는것은..
| G[node][0], G[node][1], G[node][2], G[node][3] .... G[node][size]
| 즉, "G[node]"의 배열의 크기만큼 싸그리 둘러본다는 동작.
| }
|
| 살펴볼때 기준
| 이미 방문되었나?
| no이면 들어간다. 재귀 DFS(next_node)
| yes이면 다른정점을 찾거나 빠져나온다. 재귀에서
|
ㄴ
ⓐ+1 DFS의 방문순서는 어떻게 알지??
방문체크 visit이 되는순간마다
cout을 하면 될듯 ㅋ
___________________________________________
ⓑBFS는 큐의 push pop을 이용해서 탐색한다.
DFS와는 다르게.. 이건 BFS만을 위한 queue 자료구조를
따로 한번 만들어줘야 한다.
#while : queue가 빌때까지
#for : next 주변 노드 고르기
#is visit? : yes or no
1.BFS(시작정점);
2.queue push(시작정점)
3.while(queue가 아직 뭔가 채워져있나?)
{
-채워쳐 있는 원소 front값 (정점번호)하나 가져오고
(정점번호를 popnode라고 하면)
그다음 pop한다.
-for문으로 popnode 의 주변노드 next_node를 고른다.
{
고른 next_node가 이미 방문되었나?
no : queue push(next_node)
visit[next_node] = true;
yes : 이면 다른정점을 찾아 for continue;
}
}
_______________________________________________
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 87 | #include <iostream> #include <algorithm> #include <queue> #include <string> #include <vector> using namespace std; //입력_________________________________ int N,M,S; /* N:정점 개수 M:간선 개수 S:시작정점 예를들어서.. DFS(S); 또는 BFS(S); */ //_________________________________ //배열_________________________________ vector<int> G[1001]; bool D_visit[1001]; bool B_visit[1001]; queue<int> BFS_queue; //_________________________________ void DFS(int cur) { D_visit[cur] = true; cout << cur << ' '; for (vector<int>::iterator it = G[cur].begin(); it != G[cur].end(); it++) { int nxt = *it; if(!D_visit[nxt]) DFS(nxt); } } void BFS(int cur) { B_visit[cur] = true; BFS_queue.push(cur); while (!BFS_queue.empty()) { int cur_node = BFS_queue.front(); BFS_queue.pop(); B_visit[cur_node] = true; cout << cur_node << ' '; for (int nxt : G[cur_node]) { if (!B_visit[nxt]) { BFS_queue.push(nxt); B_visit[nxt] = true; } } } } int main() { cin >> N >> M >> S; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } for (int i = 0; i < N; i++) { sort(G[i].begin(), G[i].end()); } DFS(S); cout << '\n'; BFS(S); } |
'컴퓨터 > 알고리즘' 카테고리의 다른 글
|정렬 알고리즘|버블, 선택, 삽입, 퀵, 병합, 힙 정렬 연습 (0) | 2021.02.10 |
---|---|
|코린이의 코포| Round 698 Div.2 (A, B) 참고에 도움안되는 솔브 (0) | 2021.01.29 |
[백준 11060번] 점프 점프 |DP연습| (0) | 2021.01.19 |
[백준 2606번] 바이러스 |그래프의 탐색법| (0) | 2020.12.25 |
[알고리즘 그림노트] 그래프-1 용어정리&그래프의 코드 표현법 (0) | 2020.12.24 |