[BaekJoon/백준] 2606번 C++

 BFS로 해결할 수 있는 문제였다. BFS의 기본유형을 아주 잘 나타낸 문제였던 것 같다!!

 

BFS 문제는 이 문제가 두 번째였는데, 느낌은 오는데 구현이 힘들었다.

아직 BFS에 대해 많이 익히지 못했으니까!!

 

앞으로 점점 익혀나갈 것이다.

 

어렵더라도 꼭 머릿속으로 그려가며 풀어보셨으면 좋겠다.

특히 블로그 두 군데를 추천해드릴테니, 설명을 보고

그림을 따라가면서 문제를 한번 꼭 직접 구현해봤으면 좋겠다.

참고 : 1. gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html  2. m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&proxyReferer=https:%2F%2Fwww.google.com%2F  

 

정말 도움이 많이 되었다.

BFS를 구현할 때에는 VISIT 구현이 필요하다는 것을 다시 한번 기억하자!!

그리고 연결을 구현할 때에는 서로(상호간에) 연결하여 구현해줘야 한다는것!

ex)

1과 2의 연결을 나타내고 싶을 때

1. arr[1][2] = arr[2][1] = 1;

2. vec[1].push(2); vec[2].push(1);

그리고 백터 배열을 처음으로 사용해보았다~!! 이 문제를 아예 이중배열로 구현하는 방법보다

시간복잡도가 덜 걸리는 방법이다!

 

2차원 배열일 경우에는 매 회 마다 모든 경우를 돌아줘야 하지만, 벡터 배열을 사용함으로써 특정 케이스(인덱스)별로의 크기만큼만 돌아줄 수 있었다. 이 문제는 1697번과 더불어 두고두고 다시 봐야겠다!

// 여기서 ct는 1697번의 depth와는 다른 느낌임을 주의!
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int temp1, temp2;
int ct;

vector<int> chain[101];
bool visit[101];

void bfs(int start) {
    
    queue<int> q;
    q.push(start);
    visit[start] = 1;
    
    while(q.empty() == 0) {
        
        int x = q.front(); q.pop();
        
        for(int i = 0; i < chain[x].size(); i++) {
            if(!visit[chain[x][i]]) {
                q.push(chain[x][i]);
                visit[chain[x][i]] = 1;
                ct++;
            }
        }
        
    }
    
}

int main() {

    cin >> N >> M;
    
    for(int i = 0; i < M; i++) {
        
        cin >> temp1 >> temp2;
        
        // 노드 연결
        chain[temp1].push_back(temp2);
        chain[temp2].push_back(temp1);
    }
    
    bfs(1);
    
    cout << ct;
}