[알고리즘]프로그래머스 43162번 - 네트워크

프로그래머스 43162번 - 네트워크

프로그래머스 43162번 - https://programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스 43162번 - https://programmers.co.kr/learn/courses/30/lessons/43162

 

요구사항

1. 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

2. 1번을 만족할 경우 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 말할 수 있습니다.

3. 주어진 연결 정보를 바탕으로 네트워크가 구성되어있을 때, 네트워크의 개수를 반환하라.

 

요구사항 분석 및  풀이과정

1. 문제가 어려워 보이지만 결과적으로 주어진 컴퓨터들이 몇 개의 그룹으로 묶이는지를 묻는 문제입니다.

2. 전형적인 서로소 집합(Disjoint-Set, Union-Find) 문제라고 볼 수 있습니다. 서로소 집합을 이용하여 풀어보겠습니다.

 

서로소 집합 자료구조에 대한 개념은 다루지 않겠습니다. 서로소 집합 자료구조의 구현은 다음을 참고해주세요.

 

3. 서로소 집합에서 각 집합에는 대표 원소가 존재, 나머지 원소는 자신이 속한 집합의 대표 원소를 부모로 가지고 있습니다.

4. 각 원소의 부모 원소가 자신이면 해당 원소는 집합의 대표 원소임을 의미합니다.

5. 따라서 서로소 집합들을 구성한 후, 4번을 만족하는 대표 원소의 개수가 네트워크(그룹, 집합)의 개수입니다.

 

소스코드 작성

import java.util.stream.IntStream;

class Solution {

	private static class Dsu {

		private final int[] parent;

		public Dsu(int size) {
			this.parent = new int[size];
			for (int i = 0; i < size; i++) {
				parent[i] = i;
			}
		}

		public int find(int x) {
			if (parent[x] == x) {
				return x;
			}

			parent[x] = find(parent[x]);
			return parent[x];
		}

		public boolean union(int x, int y) {
			int parentX = find(x);
			int parentY = find(y);

			if (parentX == parentY) {
				return false;
			}

			parent[parentY] = parentX;
			return true;
		}
	}

	public int solution(int n, int[][] computers) {
		Dsu d = new Dsu(n);

		for (int row = 0; row < computers.length; row++) {
			for (int col = 0; col < n; col++) {
				if (computers[row][col] == 1) {
					d.union(row, col);
				}
			}
		}

		return (int)IntStream.range(0, n).filter(v -> d.find(v) == v).count();
	}
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

이 문제를 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 로도 풀 수 있습니다. 한번 시도해보면 좋은 공부가 될 거예요.