[백준11724] 연결 요소의 개수 - 완전탐색(dfs,bfs), Union-Find, 그래프 표현(2차원배열, 연결리스트)

문제

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

11724번: 연결 요소의 개수

 

문제분석

시간복잡도

• 노드개수 V (1000개)
• 엣지개수 E ( V^2 )
• 무방향 그래프, 연결요소 파악
  1) 그래프 표현: 2차원 배열
  노드 한개와 연결된 노드를 순회하는 비용: O( V )
  → 완전탐색 비용: O( V ^ 2 ) (∵노드 개수 V개)
  
  2) 그래프 표현: 연결리스트 배열
  노드 한개와 연결된 노드를 순회하는 비용: O ( 해당 노드와 연결된 엣지의 개수 )
  → 완전탐색 비용: O( V + E )
• O (min ( V^2 , V + E ))
  노드개수와 간선개수를 비교하여 그래프표현 선택

 

참고로 두 그래프 표현의 시간복잡도를 그림으로 표현하면 아래와 같다.

 

 

문제 유형

• 그래프 탐색, 완전 탐색(dfs, bfs)
  시간복잡도 상, 그래프 표현은 2가지 모두 가능
• Union-Find
  연결요소의 개수를 파악 == 집합의 개수를 파악
  Union연산으로 집합을 합치고, Find연산과 Set 자료구조로 집합의 개수를 파악

 

dfs, bfs 설계

dfs, bfs 완전탐색 설계는 이전 포스팅을 참고.

핵심은, 연결된 곳과 갈 수 있는지 파악하는 것이다.

• 연결된 곳:
  인접리스트 배열의 경우: adj [node] 의 모든 엘레멘트들
  2차원 배열의 경우: adj [node] [1 ~ N] 의 값이 0이 아닌 1 ~ N 값
• 갈 수 있는가?
  방문하지 않은 경우

코드

인접리스트 배열 ver

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

public class BOJ11724연결요소의개수 {
	static int N, M;
	static List<Integer>[] adj;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		adj = new ArrayList[N + 1];
		visited = new boolean[N + 1];

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

		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adj[from].add(to);
			adj[to].add(from);
		}

		int areaCount = 0;
		for (int node = 1; node <= N; node++) {
			if (!visited[node]) {
				areaCount++;
//				dfs(node);
				bfs(node);
			}
		}

		System.out.println(areaCount);
	}

	private static void dfs(int node) {

		visited[node] = true;
		// base case (x)

		// recursive case
		for (int nextNode : adj[node]) {
			if (!visited[nextNode]) {
				dfs(nextNode);
			}
		}
	}

	private static void bfs(int startNode) {
		// starting point setting
		Queue<Integer> queue = new LinkedList<>();
		queue.add(startNode);

		while (!queue.isEmpty()) {
			// 방문: 큐에서 꺼내옴
			int node = queue.poll();

			// 목적지인가? (x)
			// 연결된 곳
			for (int nextNode : adj[node]) {
				// 갈 수 있는가
				if (!visited[nextNode]) {
					visited[nextNode] = true;
					// 방문예정에 등록: 큐에 넣음
					queue.add(nextNode);
				}
			}
		}
	}
}

 

 

 

2차원 배열 ver

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

public class BOJ11724연결요소의개수_2차원배열 {
	static int N, M;
	static int[][] adj;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		adj = new int[N + 1][N + 1];
		visited = new boolean[N + 1];

		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adj[from][to] = 1;
			adj[to][from] = 1;
		}

		int areaCount = 0;
		for (int node = 1; node <= N; node++) {
			if (!visited[node]) {
				areaCount++;
//				dfs(node);
				bfs(node);
			}
		}

		System.out.println(areaCount);
	}

	private static void dfs(int node) {

		visited[node] = true;
		// base case (x)

		// recursive case
		for (int nextNode = 1; nextNode <= N; nextNode++) {
			if (node != nextNode && adj[node][nextNode] == 1 && !visited[nextNode]) {
				dfs(nextNode);
			}
		}
	}

	private static void bfs(int startNode) {
		// starting point setting
		Queue<Integer> queue = new LinkedList<>();
		queue.add(startNode);

		while (!queue.isEmpty()) {
			// 방문: 큐에서 꺼내옴
			int node = queue.poll();

			// 목적지인가? (x)
			// 연결된 곳
			for (int nextNode = 1; nextNode <= N; nextNode++) {
				// 갈 수 있는가
				if (node != nextNode && !visited[nextNode] && adj[node][nextNode] == 1) {
					visited[nextNode] = true;
					// 방문예정에 등록: 큐에 넣음
					queue.add(nextNode);
				}
			}
		}
	}
}

 

 

Union-Find 설계

1. 서로소 집합 초기화
2. find 연산 구현: find (node)
   집합을 대표하는 "루트" 노드를 재귀적으로 찾아서 리턴
   루트노드: 자신의 부모가 자기자신인 노드
3. union 연산 구현: union (node1, node2)
   - find(node1), find(node2)로 각 집합의 루트노드 구하기
   - 루트노드끼리 연결
   
   

코드

public class BOJ11724연결요소의개수_유파ver {
	static int N, M;
	static int[] parent;
	static Set<Integer> groupNumbers = new HashSet<Integer>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		initialize();

		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int nodeOne = Integer.parseInt(st.nextToken());
			int nodeTwo = Integer.parseInt(st.nextToken());
			
			union(nodeOne, nodeTwo);
		}
		
		calculateGroupCount();
		
		System.out.println(groupNumbers.size());
	}

	private static void initialize() {
		parent = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
	}

	private static int find(int node) {
		if (parent[node] == node) {
			return node;
		}
		return parent[node] = find(parent[node]);
	}

	private static void union(int nodeOne, int nodeTwo) {
		int rootOne = find(nodeOne);
		int rootTwo = find(nodeTwo);
		parent[rootOne] = rootTwo;
	}
	
	private static void calculateGroupCount() {
		for(int node=1; node<=N; node++) {
			groupNumbers.add(find(node));
		}
	}
}

 

결과

 

 

기록

• 날짜: 2022-12-22 (완전탐색. dfs, bfs)
• 소요시간: 15분
• 날짜: 2022-12-23 (union-find)
• 소요시간: 10분

 

보완 사항

• 인접리스트 배열 vs 2차원 배열 시간복잡도 정확히 숙지
• 그래프 표현별 구현 방식 차이 숙지
• union-find 설계 및 구현 정확히 숙지
• union-find 경로압축 시, 시간복잡도 숙지
• union-find 유형 접근 근거 정확히 숙지
  해당 문제는 집합의 개수를 구하는 문제이므로, union으로 집합을 합치고 find + set으로 집합의 개수를 파악할 수 있을 것이라 판단