문제 풀이(5)

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

import java.util.*;
import java.io.*;


class Solution {

	static ArrayList<Integer>[] tree;

	static boolean[] visited;

	static int deleteNode = 0;
	
	static int answer = 0;

	public static void main(String[] args) {
	
		int result = solution(9,	
        new int[][] {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}});
	
		System.out.println(result);

		result = solution(4, new int[][] {{1, 2}, {2, 3}, {3, 4}});

		System.out.println(result);

	}

    public static int solution(int n, int[][] wires) {
	

		tree = new ArrayList[n + 1];

		visited = new boolean[n + 1];

		for (int i = 0; i <= n; i++) {
			tree[i] = new ArrayList<>();
		}

		for(int[] wire : wires)
		{
			tree[wire[0]].add(wire[1]);
			tree[wire[1]].add(wire[0]);
		}


		
	
		ArrayList<Integer>list = new ArrayList<>();


		for (int i = 1; i <= n; i++) {
			
			deleteNode = i;


			for (int j = 1; j <= n; j++) {
				

				
			
				int value = DFS(j);

			
				value++;
			
			
			
				list.add(value);
			

			
				visited = new boolean[n + 1];
			}

			

		}

		Collections.sort(list);

		

		int result = (int)n / 2;



		int min = Integer.MAX_VALUE;

		for (int i = 0; i < list.size(); i++) {
			
			if (Math.abs(result - list.get(i)) < min ) {
				min = Math.abs(result - list.get(i));

				answer = list.get(i);
			}

		}

		


		return Math.abs( n - answer ) - answer;
	}

	public static int DFS(int number )
	{

		

		visited[number] = true;

		int countNode = 0;

		

		for(int next : tree[number])
		{
			if(visited[next] == false && next != deleteNode){
				countNode++;
				countNode += DFS(next);
			}
		}



		return countNode;
	}
}

tree: 그래프의 인접 리스트 표현을 위한 ArrayList 배열이다. 각 노드에서 연결된 노드들을 저장한다.

visited: DFS를 통해 노드를 방문했는지 여부를 나타내는 boolean 배열이다.

deleteNode: 현재 삭제할 노드를 저장하는 변수이다.

answer: 문제의 결과를 저장하는 변수로, 최종적으로 반환되는 값이다.

DFS 메서드: 깊이 우선 탐색(DFS)을 통해 노드를 방문하고, 해당 노드를 포함한 그래프의 크기를 반환하는 메서드이다.

solution 메서드는 다음과 같은 순서로 동작한다:

입력된 노드의 갯수 n과 연결된 간선 정보를 나타내는 2차원 배열 wires를 인자로 받는다.

tree 배열과 visited 배열을 초기화하고, 인접한 노드들을 서로 연결하는 그래프를 구성한다.

노드를 하나씩 삭제해가며 각 상황에서 그래프의 구성 요소 크기를 계산하고 리스트에 추가한다.

리스트에 추가된 구성 요소 크기들을 정렬한다.

그래프를 두 개의 구성 요소로 나눌 때, 각 구성 요소의 크기가 최대한 비슷하도록 result 값을 계산한다.

list에서 result와의 차이가 가장 작은 값을 찾아 answer에 저장한다.

최종 결과인 그래프의 크기 차이를 반환한다.