[C++] 11724번 연결 요소의 개수 - 그래프 이론, BFS, DFS

#include <iostream>

#define MAX_GRAPH_SIZE 1009

using namespace std;

int graph[MAX_GRAPH_SIZE][MAX_GRAPH_SIZE];  //행렬을 이용한 그래프 구현
int N, M;  //정점의 개수 N, 간선의 개수 M
int cnt;  //연결 요소의 개수

void f(int u)
{
    if (!u) { //초기상태인가?
        for (int i=1; i<=N; i++) {
            int flag=0;
            for (int j=1; j<=N; j++) {
                if (graph[i][j]) {
                    for (int q=1; q<=N+1; q++)
                        graph[q][j]=0;
                    f(j);
                    flag=1;
                }
            }
            if(flag)
                cnt++;
        }
    }
    else {
        for (int i=1; i<=N; i++) {
            if (graph[u][i]) {
                for (int j=1; j<=N+1; j++)
                    graph[j][i]=0;  //이미 확인한 정점은 제거하기
                f(i);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=1; i<=N; i++)
        graph[N+1][i]=1;
    for (int i=0; i<M; i++) {
        int u, v;  //간선에서 연결되는 두 정점
        
        cin >> u >> v;
        graph[u][v]=1, graph[v][u]=1;
    } f(0);
    for (int i=1; i<=N; i++) {
        if(graph[N+1][i])
            cnt++;
    }

    printf("%d", cnt);
    
    return 0;
}

 

이 코드 짜느라 죽는 줄 알았다. for문에서 if문 으로 묶인 소스 하나만 있어도 대괄호를 치지 않으면 값이 다르게 나오나보다. 이것 때문에 20분 정도 소비한 것 같다.

다 풀고 나서 0ms 나온 사람의 코드를 봤는데 확실히 인접 리스트로 푸는 게 시간이 적게 걸리는 듯 하다. 하기야 인접 행렬로 풀려면 n*n의 배열을 모두 찾아봐야되니까 시간이 많이 걸릴 수 밖에 없다.

 

 

<아이디어>

https://leyamon.tistory.com/entry/11279%EB%B2%88-%EC%B5%9C%EB%8C%80-%ED%9E%99-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

[C++언어] 11279번 최대 힙 - 우선순위 큐

 

<인접 리스트로 구현>

https://www.acmicpc.net/source/15790999

로그인

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.