프로그래머스 위클리 챌린지 9주차 - java

문제 설명

1. n개의 송전탑은 트리 형태로 이어져있다.

2. 무조건 트리 형태이며, 중간에 한 칸을 끊어 두 개의 네트워크로 분할한다.

3. 두 네트워크 간의 차이의 절대값의 최소값을 return하면 된다.

풀이 과정

 1. 간단한 문제이지만 효율적인 방법으로 풀기는 생각보다 힘들다.....

 2. 먼저 모든 전선을 연결시킨다.

 3. 그리고 각각의 경우에서 자신의 경우 / 자식의 경우를 나누어, DFS를 해 준다.

 4. 모든 경우를 구하면서 연결을 끊은 경우를 구했으면, 그 연결을 해제하고, 다른 곳에서는 해당 연결을 다시 구하지 않을 것이다.

 5. 그 경우들에 대해 최소의 절대값을 구하면 답을 return할 수 있다.

코드

	class Solution {
	public static int max;
	public static int answer;
	public static boolean link[][];
	public static boolean check[];
	public int solution(int n, int[][] wires) {
	max = n;
	answer = n;
	link = new boolean[n+1][n+1];
	check = new boolean[n+1];
	for(int wire[] : wires) {
	int x = wire[0];
	int y = wire[1];
	link[x][y] = true;
	link[y][x] = true;
	}
	dfs(1);
	return answer;
	}
	public static int dfs(int num){
	int child = 1;
	for(int i=1; i<=max; i++) {
	if(check[i] || !link[num][i]) continue;
	check[i] = true;
	child += dfs(i);
	}
	answer = Math.min(answer, Math.abs(child - (max - child)));
	return child;
	}
	}

view raw 위클리 챌린지 9주차 hosted with ❤ by GitHub