[BAEKJOON] 11724번 연결 요소의 개수

---

위의 예제 입력1과 2를 그림으로 나타내었다.

그래프의 연결요소는 무방향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프를 의미하고, 연결요소의 개수는 아래의 그림과 같이 부분 그래프의 개수를 나타낸다.

 

 

먼저 입력받는 노드와 간선을 인접행렬 방식으로 이차원배열에 저장한다.

만약 노드 1번과 2번이 연결되어 있다면 arr [ 1 ] [ 2 ]와 arr [ 2 ] [ 1 ]에 1을, 연결이 안 되어 있다면 0으로 초기화한다.

1번과 2번이 연결되어 있다는 것은 2번과 1번이 연결되어 있다는 것과 같으므로 값을 두 번 저장하는 과정이 필수이다.

(전역변수로 선언할 예정이기 때문에 모든 요소가 자동으로 0으로 초기화됨)

전체 노드를 순회하면서 아직 방문하지 않았으면 재귀 호출 방식으로 연결된 노드들을 탐색한다.

 

• DFS  이차원 배열

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

public class Main {
	static int arr[][], N, cnt;
	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()); // 정점 개수
		int M = Integer.parseInt(st.nextToken()); // 간선 개수
		arr = new int[N + 1][N + 1];
		visited = new boolean[N+1];
		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			arr[i][j] = 1;
			arr[j][i] = 1;
		}
		for (int i = 1; i < N+1; i++) {
			if (!visited[i]) {
				dfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);
	}

	static void dfs(int i) {
		visited[i] = true;
		for (int k = 1; k <= N; k++) {
			if (arr[i][k] == 1 && !visited[k])
				dfs(k);
		}
	}
}

 

같은 방식으로 이차원 배열 인접행렬 방법을 이중 ArrayList로 구현하였다.

• DFS, ArrayList 사용

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

public class Main {
	static int N, cnt;
	static boolean visited[];
	static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();

	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()); // 정점 개수
		int M = Integer.parseInt(st.nextToken()); // 간선 개수
		visited = new boolean[N+1];
		for(int i = 0; i <= N; i++) {
            arr.add(new ArrayList<>());
        }

		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			arr.get(i).add(j);
			arr.get(j).add(i);
		}
		for (int i = 1; i < N+1; i++) {
			if (!visited[i]) {
				dfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);
	}

	static void dfs(int i) {
		visited[i] = true;
		for (int k = 0; k < arr.get(i).size(); k++) {
			if (!visited[arr.get(i).get(k)])
				dfs(arr.get(i).get(k));
		}
	}
}

 

다음으로 Queue를 활용한 BFS이다. 자기자신과 연결된 노드들을 큐에 저장하여 다음 순서에서 꺼낸 노드와 연결된 노드를 계속해서 탐색하는 방식이다. 

• BFS, ArrayList 사용

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 {
	static int N, cnt;
	static boolean visited[];
	static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();

	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()); // 정점 개수
		int M = Integer.parseInt(st.nextToken()); // 간선 개수
		visited = new boolean[N+1];
		for(int i = 0; i <= N; i++) {
            arr.add(new ArrayList<>());
        }

		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			arr.get(i).add(j);
			arr.get(j).add(i);
		}
		for (int i = 1; i < N+1; i++) {
			if (!visited[i]) {
				bfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);
	}

	static void bfs(int i) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		visited[i] = true;
		
		while(!queue.isEmpty()) {
			i = queue.poll();
			for (int k = 0; k < arr.get(i).size(); k++) {
				if (!visited[arr.get(i).get(k)]) {
					queue.add(arr.get(i).get(k));
					visited[arr.get(i).get(k)] = true;
				}
			}
		}
	}
}

 

[출처]

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

11724번: 연결 요소의 개수