[BOJ] 1260. DFS와 BFS(DFS, BFS)

#. Problem

https://www.acmicpc.net/problem/1260

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

- 입력으로 주어지는 간선은 양방향

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

DFS와 BFS의 기본! 문제다.

여기서 

  - 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

  - 입력으로 주어지는 간선은 양방향

처음에 이 두 조건을 못 보고 지나갔다가

계속 안 풀려서 허우적 허우적 거렸었다ㅋㅋㅋㅋ

아무리 쉬워보이는 문제더라도 문제를 꼼꼼히 읽어야지..

#. Code

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

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std;   int N, M, V;    // 정점 개수, 간선 개수 vector<int> ch; vector<vector<int> > vt;   void DFS(int s) {     int i;     if (ch[s]) return;          ch[s] = 1;     printf("%d ", s);     for (i = 0; i < vt[s].size(); i++) {         DFS(vt[s][i]);     } }   void BFS(int s) {     int i;     vector<int> ch2(N + 1);     queue<int> q;       q.push(V);     while (!q.empty()) {         int x = q.front();         q.pop();         if (!ch2[x])             printf("%d ", x);         ch2[x] = 1;           for (i = 0; i < vt[x].size(); i++) {             if (!ch2[vt[x][i]])                 q.push(vt[x][i]);         }     } }   int main(void) {     int i, a, b;     // freopen("input.txt", "rt", stdin);     scanf("%d %d %d", &N, &M, &V);       vt.resize(N + 1);     for (i = 0; i < M; i++) {         scanf("%d %d", &a, &b);         vt[a].push_back(b);         vt[b].push_back(a);     }       for (i = 1; i <= N; i++)          sort(vt[i].begin(), vt[i].end());          // DFS     ch.resize(N+ 1, 0);     DFS(V);       puts("");       // BFS     BFS(V);       return 0; } Colored by Color Scripter

cs

#. Other Code

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

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std;   int N, M, V;    // 정점 개수, 간선 개수 vector<int> ck; vector<vector<int> > vt;   void DFS(int s) {     int i;     printf("%d ", s);     for (i = 0; i < vt[s].size(); i++) {         if (!ck[vt[s][i]]) {             ck[vt[s][i]] = 1;             DFS(vt[s][i]);         }     } }   void BFS(int s) {     int i;     vector<int> ck2(N + 1);     queue<int> q;       q.push(V);     ck2[V] = 1;     while (!q.empty()) {         int x = q.front();         q.pop();              for (i = 0; i < vt[x].size(); i++) {             if (!ck2[vt[x][i]]) {                 q.push(vt[x][i]);                 ck2[vt[x][i]] = 1;             }         }           printf("%d ", x);     } }   int main(void) {     int i, a, b;     // freopen("input.txt", "rt", stdin);     scanf("%d %d %d", &N, &M, &V);       vt.resize(N + 1);     for (i = 0; i < M; i++) {         scanf("%d %d", &a, &b);         vt[a].push_back(b);         vt[b].push_back(a);     }       for (i = 1; i <= N; i++)          sort(vt[i].begin(), vt[i].end());          // DFS     ck.resize(N+ 1, 0);     ck[V] = 1;     DFS(V);       puts("");       // BFS     BFS(V);       return 0; } Colored by Color Scripter

cs

* 위 코드랑 로직은 같은데 더 간결하게 다시 작성해 보았다.

line 52) 인접리스트를 만들기 위해 이차원 벡터를 사용

line 53~57) "입력으로 주어지는 간선은 양방향"

line 59~60) "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"

line 64) 시작 정점은 이미 방문한 상태이므로 미리 check

line 11~21) DFS

line 14) 재귀함수로 들어오면 바로 정점을 출력

line 15~20) 해당 정점과 연결된 정점들을 탐색

line 16~19) 해당 정점과 연결되어있는 정점들 중 방문하지 않았던 정점이면

line 17) 방문을 할꺼니까 check 해주고

line 18) 방문하지 않은 정점으로 재귀함수를 호출

line 23~44) BFS 는 보통 Queue 를 사용

line 29) 시작 정점을 Queue 에 넣어주고,

line 30) 시작 정점은 이미 방문한 상태이므로 미리 check

line 31~43) Queue 가 빌 때까지 반복

line 32) Queue 의 가장 앞에 있는 값을 빼주고

line 35~40) 해당 정점과 연결된 정점이 있을 경우 탐색

line 36~40) 해당 정점과 연결되어있는 정점들 중 방문하지 않았던 정점이면

line 37) 방문할 예정이므로 Queue 에 넣어주고

line 38) check !

line 42) Queue에서 빼낸 정점을 출력