프로그래머스_전력망을 둘로 나누기(JAVA)

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

프로그래머스

[문제 풀이]

BFS을 이용하여 문제를 풀었습니다.

 

트리가 주어졌을 때 간선을 하나 끊어서 양쪽 노드의 갯수의 차이가 최소인 것을 구하는 문제입니다. 아이디어는 다음과 같습니다. 주어진 트리를 기록할 이차원 배열을 선언하여 기록하여 줍니다. 그 후 간선을 하나씩 뽑으면서 이차원 배열에 기록된 간선을 지워주고 한쪽 노드의 갯수를 구하여 차이를 구합니다.

 

구현한 방식은 아래와 같습니다.

1. MAP[노드의 크기 + 1][노드의 크기 + 1]의 이차원 배열을 지정해 줍니다.
2. 주어진 트리정보를 순회하면서 이차원 배열의 간선의 정보를 기록해 줍니다.
3. 주어진 트리정보를 순회하면서 선택 된 간선의 기록을 MAP에서 지워줍니다.
4. BFS에서 큐에 노드를 넣습니다.
5. 방문 배열에 방문 기록을 해줍니다.
6. 선택된 노드에 달려있는 노드들의 갯수를 세어주며 큐에 넣습니다.
7. 전체를 반복한후 전체노드 - (2 * 한쪽노드의 수)중 가장 작은 수를 구합니다.

[JAVA]

import java.util.LinkedList;
import java.util.Queue;

class Solution {

	boolean[][] MAP;
	
	public int solution(int n, int[][] wires) {
		int answer = 987654321;
		
		MAP = new boolean[n + 1][n + 1];
		
		for(int[] item : wires) {
			MAP[item[0]][item[1]] = true;
			MAP[item[1]][item[0]] = true;
		}

		for (int i = 0; i < wires.length; i++) {
			
			MAP[wires[i][0]][wires[i][1]] = false;
			MAP[wires[i][1]][wires[i][0]] = false;
			
			answer = Math.min(answer, BFS(n, wires[i][0]));

			MAP[wires[i][0]][wires[i][1]] = true;
			MAP[wires[i][1]][wires[i][0]] = true;

		}

		return answer;
	}

	public int BFS(int n, int start) {

		boolean[] visited = new boolean[n+1];
		int cnt = 1;
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);

		while(!queue.isEmpty()) {
			int pos = queue.poll();
			visited[pos] = true;
			
			for(int i = 1; i <= n; i++) {
				if(visited[i] == false && MAP[pos][i] == true) {
					queue.add(i);
					cnt++;
				}
			}
		}
		return (int)Math.abs(n - (cnt * 2));
	}
	
}