[프로그래머스] 86971번 자바(Java) 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

문제

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

입력

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

풀이

시간, 공간 복잡도

• 시간: O(v*(n+v)), 부가설명: (간선 하나씩 없는 경우)*(간선과 연결된 노드를 통한 방문)
• 공간:

풀이과정

• 간선 하나씩 없다고 가정하고 나눠진 전력망 1,2,의 개수를 cnt해서 비교한다.
• 전력망 1,2의 개수는 bfs를 이용한다

기존

간선1 없다고 가정

 

간선 3이 없다고 가정

이런 과정으로 간선 8까지 돌았을때 3의 차이가 제일 min이다.

따라서 답은 3이다.

 

 

예제 입력 예시

n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

 

예제 출력 예시

3

 

소스코드

import java.util.*;

class Solution {
	public int solution(int n, int[][] wires) {
		int answer = n;
		int len = wires.length;
		
		//반복 필요, 각 케이스는 한 간선을 제외하고 실시 필요
		for (int t = 0; t < len; t++) {
			boolean[] visited = new boolean[n+1];
			ArrayList<Integer>[] graph = new ArrayList[n+1];
			int count1 = 0;  //전력망1 갯수
			int count2 = 0;  //전력망2 갯수
			int graphCount = 0;  //총 전력망 갯수
			for (int i = 0; i < graph.length; i++) {
				graph[i] = new ArrayList<>();
			}
			
			for (int i = 0; i < len; i++) {
				if(i == t)continue;
				int n1 = wires[i][0];
				int n2 = wires[i][1];			
				graph[n1].add(n2);
				graph[n2].add(n1);
			}

			for(int i = 1; i< n+1; i++) {
				if(!visited[i]) {
					graphCount++;
					if(graphCount == 1) {
						count1++;
					}else {
						count2++;
					}
					Queue<Integer> queue = new LinkedList<>();
					queue.add(i);
					visited[i] = true;
					while(!queue.isEmpty()) {
						int cur = queue.poll();
						for(int num :graph[cur]) {
							if(!visited[num]) {
								visited[num] = true;
								queue.add(num);
								if(graphCount == 1) {
									count1++;
								}else {
									count2++;
								}
							}
						}
					}
				}
			}
			if(graphCount == 2) {
				int differ = Math.max(count1, count2) - Math.min(count1, count2);
				if(differ<answer) {
					answer = differ;
				}
			}
		}
		return answer;
	}
}