230929 전력망을 둘로 나누기

private int[][] adjacencyMatrix;

public int solution(int n, int[][] wires) {
	int answer = n;
	adjacencyMatrix = new int[n + 1][n + 1];

	initializeAdjacencyMatrix(wires);

	for (int i = 0; i < wires.length; i++) {
		int x = wires[i][0];
		int y = wires[i][1];

		removeWire(x, y);
		answer = Math.min(answer, calculateMinDifference(n, x));
		addWire(x, y);
	}

	return answer;
}

private void initializeAdjacencyMatrix(int[][] wires) {
	for (int[] wire : wires) {
		int x = wire[0];
		int y = wire[1];
		adjacencyMatrix[x][y] = 1;
		adjacencyMatrix[y][x] = 1;
	}
}

private void removeWire(int x, int y) {
	adjacencyMatrix[x][y] = 0;
	adjacencyMatrix[y][x] = 0;
}

private void addWire(int x, int y) {
	adjacencyMatrix[x][y] = 1;
	adjacencyMatrix[y][x] = 1;
}

private int calculateMinDifference(int n, int start) {
	int[] visited = new int[n + 1];
	int cnt = 1;

	Queue<Integer> queue = new LinkedList<>();
	queue.offer(start);

	while (!queue.isEmpty()) {
		int point = queue.poll();
		visited[point] = 1;

		for (int i = 1; i <= n; i++) {
			if (visited[i] == 1) {
				continue;
			}
			if (adjacencyMatrix[point][i] == 1) {
				queue.offer(i);
				cnt++;
			}
		}
	}

	return Math.abs(n - 2 * cnt);
}

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