백준 11724. 연결요소의 개수 구하기

문제 11724. 연결요소의 개수 구하기

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

bfs는 적용안해봤고, dfs를 이용하여 풀이해보았다.
dfs의 가장 기초적인 문제라 크게 어려울 건 없다. 한 정점에서 연결되어 있는 정점들끼리 뻗을 수 있는 곳까지 다 뻗어보면 된다. 뻗어가면서 방문한 정점들을 방문처리해주면서 구해보도록 한다.

아, 이 문제에서 내가 헷갈렸던 부분은 무방향 그래프라 연결되어있는 두 정점에 서로의 값을 넣어줘야하는 부분이었다.
아래의 두 가지 경우로 예를 들어보자.

input case 1
6 5
1 2
2 5
5 1
3 4
4 6

input case 2
3 2
1 2
3 2

case1에서는 코드작성에서 양방향에 대한 처리를 안해줘도 값이 제대로 나온다. 그니까 내가 처리를 안하려던 이유는 case1 같은 경우, 정점1이 정점2와 연결되어있다. 그러므로 정점1에서 시작하면 정점1은 visited[1] = true가 될 것이고, 1에서 파생된 정점2를 방문하고 정점2에서 다시 정점1로 방문해봤자 이미 방문처리가 되었기 때문에 방문할 필요가 있는가 싶어서 기존 코드에서는 한쪽 방향에 대한 값 저장만 작성하였다.

하지만 case2를 보자 1은 2와 연결되어있고, 3은 2와 연결되어있다. 그러면 1은 3과 연결되어있는 것이다.
하지만 양방향 처리를 해주지 않으면 1에서 2로 향하고 2에서는 더이상 향할 곳이 없다.
그래서 값이 잘못 나오게 된다.

풀이 코드 python

import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
result = 0

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


def dfs(graph, start, visited):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            dfs(graph, i, visited)

for i in range(1,n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        result += 1

print(result)

풀이 코드 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

class boj11724 {
    static ArrayList<Integer>[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        arr = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        int result = 0;

        for (int i = 1; i < n + 1; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());

            arr[u].add(v);
            arr[v].add(u);
        }

        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                dfs(i);
                result++;
            }
        }

        System.out.println(result);
    }


    public static void dfs(int start){
        if (visited[start])
            return;

        visited[start] = true;
        for (Integer integer : arr[start]) {
            if (!visited[integer])
                dfs(integer);
        }
    }
}