반응형
문제 출처 :
https://www.acmicpc.net/problem/1260
알고리즘 분석 :
문제 해결에 필요한 사항
1. DFS 그리고 Stack의 관계
2. BFS 그리고 Queue의 관계
이 문제에 대한 자세한 DFS와 BFS는 알고리즘 게시판에 수록하도록 하려 한다.
DFS :: http://www.crocus.co.kr/520
BFS :: http://www.crocus.co.kr/521
이 문제에서 조심해야될 사항은
<<단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. >>
이 부분인데, 여기서 정점 번호가 작은 것을 먼저 방문한다는 것은,
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 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 88 89 90 91 92 93 94 95 96 97 98 99 | #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <queue> using namespace std; int check[1001]; vector<int> vc[1001]; queue<int> q; int V, E, start; int from, to; bool dfs(int pos) { printf("%d ", pos); check[pos] = 1; for (int i = 0; i < vc[pos].size(); i++) { int next = vc[pos][i]; if (check[next] == 0 && !dfs(next)) return false; } return true; } bool bfs(int pos) { while (!q.empty()) { // 방문을 시작하는 정점을 확인 int front = q.front(); q.pop(); if (check[front] == 0) { printf("%d ", front); check[front] = 1; } // 그 정점과 연결되어있는 정점을 확인 for (int i = 0; i < vc[front].size(); i++) { if (check[vc[front][i]] == 0) { q.push(vc[front][i]); printf("%d ", vc[front][i]); check[vc[front][i]] = 1; } } } return true; } int main() { scanf("%d%d%d", &V, &E, &start); // 무방향 그래프 형성 for (int i = 0; i < E; i++) { scanf("%d%d", &from, &to); vc[from].push_back(to); vc[to].push_back(from); } // 내림차순 정렬 for (int i = 0; i < V; i++) sort(vc[i].begin(), vc[i].end()); // DFS start dfs(start); // 연결되어 있지 않은 그래프가 있을수도 있으니 // 정점 모두를 탐색 for (int j = 1; j <= V; j++) { if (check[j] == 0) dfs(j); } printf("\n"); // 초기화 fill(check, check + 1001, 0); // BFS start q.push(start); bfs(start); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[13415번] 정렬 게임 (0) | 2016.11.10 |
---|---|
[2805번] 나무 자르기 (0) | 2016.11.10 |
[2167번] 2차원 배열의 합 (0) | 2016.11.08 |
[1652번] 누울 자리를 찾아라 (0) | 2016.11.08 |
[1987번] 알파벳 (0) | 2016.11.08 |