[백준] 11724 : 연결요소의 개수

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

11724번: 연결 요소의 개수

연결요소의 개념에 대해 공부했다.

연결요소란 그래프를 이루는 '모두 연결된 작은 그래프'의 개수이다.

개별의 그래프를 합쳐둔 느낌이라 DFS나 BFS를 사용했을 때 한 번에 전체탐색이 어려울 것 같아서, for문을 사용하여 모든 노드를 시작점으로, 시작점이 방문되지 않은 상태면  DFS나 BFS를 실행하여 실행횟수를 답으로 출력했다.

 

내 코드

메모리 : 142020 KB

시간 : 652 ms

코드길이 : 1854 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static ArrayList<Integer>[] list;
	public static boolean[] isVisit;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N + 1];
		isVisit = new boolean[N + 1];
		int result = 0;
		
		//인접리스트 초기화
		for(int n = 0; n < N + 1; n++) {
			list[n] = new ArrayList<Integer>();
		}
		
		//인접리스트 생성
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			list[u].add(v);
			list[v].add(u);
		}
		
		for(int i = 1; i <= N; i++) {
			if(!isVisit[i]) {
				BFS(i);
				result++;
			}
		}
		sb.append(result);
		System.out.print(sb);
		
	}
	//너비 우선 탐색
	public static void BFS(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(node);
		isVisit[node] = true;
		
		while(!queue.isEmpty()) {
			int nowNode = queue.peek();
			//꺼낸 노드와 연결된 노드들 체크
			for(int i = 0; i < list[nowNode].size(); i++) {
				//연결된 노드가
				int nextNode = list[nowNode].get(i);
				//방문 전 노드이면
				if(!isVisit[nextNode]) {
					//방문으로 체크한 후
					isVisit[nextNode] = true;
					//큐에 넣어줌
					queue.offer(nextNode);
				}
			}
			//탐색 끝난 노드는 큐에서 제거
			queue.poll();
		}
	}

}

 

1등코드

메모리 : 11436 KB

시간 : 76 ms

코드 길이 : 1037 B

 

[1등 코드]

class Main {

    public static void main(String[] args) throws Exception {

        int N = read();
        int M = read();
        int[] set = new int[N + 1];
        int connectedComponent = N;

        for (int i = 0; i <= N; i++) set[i] = -1;

        while (M-- > 0)
            if (union(read(), read(), set))
                if (--connectedComponent == 1) break;

        System.out.print(connectedComponent);

    }

    private static boolean union(int u, int v, int[] s) {

        if ((u = find(u, s)) == (v = find(v, s)))
            return false;

        if (s[u] < s[v]) {
            s[u] += s[v];
            s[v] = u;
        } else {
            s[v] += s[u];
            s[u] = v;
        }

        return true;
    }

    private static int find(int u, int[] s) {
        return s[u] < 0 ? u : (s[u] = find(s[u], s));
    }

    static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}