코테 일기(6) : 백준 [1260번] DFS와 BFS(BFS편)

CodeUp으로 몸? 뇌?를 풀어줬으니, 이제 알고리즘의 꽃인 백준 온라인 저지로 입성하자.

처음 접한 문제는 DFS, BFS를 다루는 문제였다.

그래프 탐색 알고리즘은 알고리즘 필수 요소 중 하나이기 때문에 절대적으로 짚고 넘어가야 한다.

BFS는 Breath-First Search 이다.

즉 depth를 한 단계씩 내려가면서 너비를 위주로 탐색하는 너비우선탐색이다.

예제 입력 2번과 같은 경우 3번에서 1, 4번을 먼저 방문 한 후에

1번에서 2번, 4번에서 5번을 방문하는 결과가 나온다.

즉 3 (1 4) (2 5) 와 같은 결과가 나와야 한다.

처음 든 생각

정점(Node)의 개수가 N이고 간선의 개수가 M이면 탐색은 M번이 이루어 져야 한다. 

{ for(int i = 0; i<M ; i++) cin >> srt >> dst; }

정점의 개수가 N 이기에 결과는 N개가 출력되어야 한다 { for(int i=0; i< N; i++) cout }

...

이후 아무 생각이 나지 않았다. 5년전에 배웠던 자료구조.. 다시 끄집어 내기 위해 구글링을 해 보았다.

queue를 사용하면 간단히 할 수 있다기에, queue 사용법도 찾아보았다.

내가 생각해 보았던 방법은 먼저 2차원 배열을 선언해 연결된 노드를 모두 1로 만들어 주고,

 

방문했던 노드는 지나치고 출력을 하면서 큐를 pop하는 것이었다.

무작정 코드를 써내려 보았다.

...

2시간이 지난 지금 2차원 동적 배열로는 도저히 답이 없다는 것을 깨닫고 vector 공부를 시작했다.

그로부터 1시간이 더 지난 지금 문제를 해결했다. 결국 STL 지식 부족의 문제였다.

코드(main을 제외한 함수만)

void bfs(int n, int m, int v) {

             vector<vector<int> > arr(n, vector<int>(n, 0)); //n X n 의 크기를 가진 벡터 할당

             int srt, dst;

             int* check = new int[n] {0}; //방문을 확인하기 위한 값

             for (int i = 0; i < m; i++) {

                           cin >> srt >> dst;

                           arr[srt-1][dst-1] = arr[dst-1][srt-1]=1; 

//해당하는 배열 값 1로 초기화

             }                           

 

             cout << v << " "; //첫번째 노드를 출력

             queue<int> q;

             q.push(v); //큐에 첫번째 노드를 push

             check[v - 1] = 1;

             for (int i = 0; i < m; i++) { //두번째 노드부터 계산

                           int frontQ=0;

                           if (q.size() != 0) { //큐의 사이즈가 0이 아니라면

                                       frontQ = q.front(); 

 //큐의 가장 앞의 값을 받아옴. 즉, 현재 노드

                                       q.pop();//사용된 노드는 제거

                           }

                           else { //큐의 크기가 0이되면 모든 pop이 끝났으므로 종료

                                        break;

                           }

                           for (int j = 1; j < n+1; j++) {

                                        if (arr[frontQ-1][j-1] == 1 && check[j-1]==0) { 

  //큐의 가장 앞의 값이 중복되지 않게함 

                                                q.push(j); //큐에 값을 집어넣음

                                                check[j-1] = 1; //중복되지 않게 flag 설정

                                                cout << j << " ";

                                        }

                           }

             }

}

Queue와 Vector를 사용할 줄 알았으면 금방 해결 할 수 있었을것 같다.

Copy & Paste는 하지 않았지만 STL 지식 부족으로 구글을 참조 할 수 밖에 없었다.

Array에 변수를 넣어 동적 할당 하고 싶다면

new보단 vector가 사용하기 간편하고 쉬운 것 같다.

하지만 아직 채점은 안해보았다 ㅎ... DFS까지 끝내고 채점을 해봐야 하기에...

다음시간엔 DFS로 해보겠다