[유니온 파인드, bfs] 백준 11724번 연결 요소의 개수 c++, java 풀이

BOJ 11724번 연결 요소의 개수 c++ 및 java 풀이

• 난이도: 실버3
• 백준 11724번 연결 요소의 개수
  
  
  

문제 정리

방향 없는 그래프가 주어질때 그래프의 연결 요소(Connected Component)의 개수를 구하시오

연결 요소 란??

그래프는 여러 개의 고립된 그래프로 구성될 수 있는데
서로 연결된 여러 개의 고립된 그래프 각각을 연결 요소라고 한다.

1. 연결 요소의 특징

• 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다.
• 또 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다.
  BFS, DFS를 통해 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결성분이 된다.
  
  
  

문제 접근

처음에 주어진 예제를 잘못 보고 문제를 이해를 잘 못해서 빨리 풀지 못했습니다 ㅠㅠㅠ
예제를 똑바로 봅시다!!!

1. 하나의 정점에서 시작해서 bfs나 dfs를 통해 연결된 점들을 탐색하며 방문 여부를 저장해주면 됩니다.
2. 그렇게 하면 하나의 정점에서 연결된 점들을 모두 탐색하게 되고 하나의 연결 요소를 찾게된 것입니다.
3. 다음 탐색시에 방문여부를 가지고 판단하여 방문하지 않은 경우 다시 bfs나 dfs를 통해 탐색하게 되면 이는 또 다른 새로운 연결요소를 탐색함을 의미합니다.

이 방법 외에도 union find를 이용하면 시간 단축을 할 수 있습니다

java 문제 풀이

1. 좀 더 효율적인 탐색을 위해 2차원 arraylist로 graph 정보를 저장합니다.
2. 저장하기 위해 초기화를 합니다
3. 그래프 연결 정보를 받아 graph 변수에 저장합니다.
   무방향 그래프이기 때문에 반대로도 연결정보를 저장해주어야 합니다.
   예를들어 1과2가 연결되어있다면 2와 1도 연겨되어 있는 것이므로 반대로도 저장해주어야 합니다.
4. 방문하지 않았다면 bfs를 통해 방문합니다.
5. bfs는 시작 정점에서 연결된 정점들을 차례차례 방문해나갑니다.
6. 방문하지 않았다면 방문처리 하고 queue에 다음 탐색을 위해 넣습니다.
7. 이를 queue가 빌 때까지 반복합니다.
8. bfs 함수를 진입하는 횟수가 연결요소의 개수가 됩니다.
   
   
   

c++ 문제풀이

c++도 java와 로직은 똑같습니다. 다만 2차원 arrayList 대신 2차원 vector를 사용합니다.

1. 2차원 벡터를 초기화합니다. vector에 N개의 빈 vector를 넣어주면 N개의 vector를 담은 2차원 vector가 됩니다.
2. graph.at(a).push_back(b) 은 자바의 graph.get(a).add(b)와 같습니다.
   vector에서 get은 at
   vector에서 add는 push_back
3. bfs도 마찬가지입니다. 다만 다른점은 vector의 iterator를 생성하여 그 정점과 연결된 다른 정점들을 하나씩 보며 방문여부를 확인합니다. 자바에서는 다음 구문과 같습니다.

    for(int b : graph.get(a)){
        // 생략
    }

4. iterator의 시작을 begin으로 받아서 포인터를 하나씩 증가시키면서 값을 참조할 수 있습니다. iterator의 끝은 end로 확인합니다.
   
   
   

union find 풀이

저는 parent 배열로 부모의 정보만 저장하였지만 여기에 rank 배열을 하나 더 만들어 높이를 맞추어가면서 하면 시간 단축을 더 할 수 있습니다.
rank를 안하게 되면 편향된 그래프의 경우 시간이 오래걸릴 수 있습니다.

1. 우선 parent 배열을 초기화 합니다. parent 배열은 각 점의 부모 노드를 담고 있습니다. 예를들어 parent[1] = 3 이면 1번 점의 부모는 3번이 됩니다.
2. 처음에는 각 점의 부모를 자기 자신으로 합니다.
3. 그리고 선의 정보를 입력받고 부모 노드를 구합니다.
4. 부모가 같지 않다면 union 함수를 통해 두 점을 이어줍니다. 즉 부모를 갖게 만들어 줍니다.
5. set을 통해 서로 다른 부모를 가지는 점의 개수를 구할 수 있습니다. 부모가 다르다는 것은 고립된 그래프이기 때문에 연결요소의 개수가 됩니다.
6. 부모를 찾느 findParent 함수는 올라갈때마다 부모의 정보를 바꿔주면서 부모를 찾아 올라갑니다. parent[x] = x일때 그 점 x가 부모가 됩니다. ( 최상위 루트의 점은 자기 자신을 부모로 하기 때문)
   
   
   

백준 11724 연결 요소의 개수 c++코드 (bfs)

 

백준 11724 연결 요소의 개수 c++코드(유니온 파인드)

백준 11724 연결 요소의 개수 java코드(bfs)

 

풀이인증

많이도 틀렸네요 ㅠㅠ

처음에는 코드 잘못 짜서 틀리고

bfs 풀이로 푸는거 맞추었다가

다시 유니온 파인드로 풀어보다가 클래스이름 모르고 안바꿧다가 런타임 에러만 2번 ㅠㅠ

맨 위의 풀이가 유니온 파인드로 제출했을때 실행시간 입니다!!!