[프로그래머스(Programmers)][자바(java)] (Lv2) 9주차 - 전력망을 둘로 나누기 <위클리 챌린지>

 

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

코딩테스트 연습 - 9주차_전력망을 둘로 나누기

 

문제 풀이

 

import java.util.*;

class Solution {

	int N, d_min; // difference in the num of towers (+min => answer)
	boolean e[][], b[]; // edge arr, is visited?
	public int solution(int n, int[][] wires) {
		e = new boolean[n][n]; int u, v; // 
		b = new boolean[n];
		for (int[] w : wires) {
			u = --w[0];
			v = --w[1];
			e[u][v] = e[v][u] = true;
		}
		N = d_min = n;
		dfs(0);
		return d_min;
	}
	public int dfs( int i ) {
		b[i] = true;
		int s = 1, d;
		for (int j = 0; j < N; ++j) { // adjacent node
			if (!b[j] && e[i][j]) {
				b[j] = true;
				s += dfs(j);
			}
		}
		d = Math.abs(2 * s - N);
		d_min = d_min > d ? d : d_min;
		return s;
	}
}

 

0번 노드(문제에서는 1번 노드)를 루트 노드라고 가정.
각 노드의 서브 노드의 개수를 각각 구함 ( dfs )
개수가 가장 많은 노드와의 연결을 끊은 후 두 전력망의 송전탑 개수 차를 구함