백준, BOJ, 11724번 C++ [CPP]

음

처음은 헤맸던 문제다.

BFS를 너무 많이써서 이번엔 DFS로 해결하였다.

 

시간도 메모리도 충분하다

음,,3초면 연산이 15번정도면 되려나...?

O(N^2)도 통과될 느낌이다.

 

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

 

---

 

 

#틀린 풀이와 맞은 풀이를 같이 두었다.

#include<iostream>
#include<vector>
#include<stack>


using namespace std;

int N, M ; // 노드, 간선
vector<int> node[1001]; // 노드에 연결된 노드의 정보를 담는 배열 ex) 1번 노드에 연결된 정보를 가리키는 벡터가 있음
int visited[1001];
int cnt = 0;

stack<int> stk; //DFS를 위함

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    
    /*
    //이렇게 하려면... 사전순으로 정리해야함 -> 입력을 사전순으로 받아야함.
    for(int i = 0; i<M; i++){
        int a,b;
        cin >> a >> b;
        //어느 한 노드라도 이미 방문되었다면 -> 그것은 연결되어있는 요소
        if(visit[a] != 0 || visit[b] != 0){
            visit[a] = 1;
            visit[b] = 1;
        }else{ // 둘다 방문하지 않았으면 새로운 연결요소
            visit[a] = 1;
            visit[b] = 1;
            cnt++;
        }
    }
    */
    
    //노드에 연결상태를 담고싶음
    for(int i = 1; i<= M; i++){
        int n1, n2;
        cin >> n1 >> n2;
        //n1노드에 연결된 n2 상태추가 , 쌍방향이므로 n2에 n1정보 추가
        node[n1].push_back(n2);
        node[n2].push_back(n1);
        
    }
    
    //DFS나 BFS 조사
    //전 노드에 대해서
    for(int i = 1; i<=N; i++){
        
        //방문했으면 다음 거
        if(visited[i] == 1) continue;
        
        //방문안했으면 
        stk.push(i);
        cnt++;
        visited[i] = 1;
        
        // DFS 실행
        while(!stk.empty()){
            int cur = stk.top();
            visited[cur] = 1;
            stk.pop();
            
            //node[i]에 연결되어있는 노드 다 집어넣음
            if(!node[cur].empty()){
                for(int a : node[cur]){
                    if(visited[a] == 1)continue; // 이미 방문한노드는 집어넣지 않음.
                    stk.push(a);
                }
            }else{ // 아무것도 연결되어있지 않다면 pass
                continue;
            }
        }    
    }

    cout << cnt;
}

 

 

음.. DFS의 의미대로

모든 노드를 조사하되

visited된 노드는 조사하지 않고

처음 노드를 stack에 넣고

뺀 다음 그 노드에 저장된 다른 노드의 정보를 다 넣고

그 노드에 맨 위를 꺼내서..

..반복

 

전 노드를 반복하기 때문에 

노드 연결정보를 가지고 있지 않은 노드도 있을텐데 그때는 어차피.. 바로 종료되어서 상관없겠지만..

else로 예외처리해줬다.

 

연결상태란

그냥 그 그림 문제랑 같다.

모여있는 조각들이 몇개냐 그거다.

 

---

 

내가 틀린 풀이라고 적어놨지만

뭐 정렬을 어떻게 하느냐에따라 저게 정답이 될 수 있다

 

다만 정렬을 어떻게 해야하냐면..

1,2가 처음 노드라면

그 뒤에는 2로 시작하는 모든것이 와야하고..

(2,7)이 마지막이라면

7로시작하는 모든것이 와야한다..

즉, BFS랑 다를 바가 없다

N(N-1)/2번 정렬을 해야할 것같으므로.. 패스