99클럽 코테 스터디 24일차 TIL 완전탐색(전력망을 둘로 나누기)

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

프로그래머스

 

 

<아이디어>

모든 전선들 중 하나를 차례대로 끊어보면서 각각의 송전탑의 차이를 구했다.

 

1. j번째 전선 끊고 전력망 연결

for(int j=0; j<len; j++){
	// i번째 송전탑 연결 무시
	if(i == j) continue;
	int x = wires[j][0];
	int y = wires[j][1];
	list[x].add(y);
	list[y].add(x);
}

 

2. 어느 하나의 노드에 연결되어 있는 송전탑 개수 계산

public static void dfs(int x){
	visited[x] = true;
	for(int i=0; i<list[x].size(); i++){
	int now = list[x].get(i);
	if(visited[now]) continue;
		cnt++;
		dfs(now);
	}
}

 

3. 두 전력망 송전탑의 개수 차의 최솟값 갱신 (cnt, (n-cnt) 차의 절댓값)

// 두 전력망의 송전탑 차의 최솟값 갱신
answer = Math.min(answer, Math.abs(n - 2 * cnt));

 

 

<제출코드>

import java.util.*;

class Solution {
    
    static int answer = Integer.MAX_VALUE;
    static int cnt = 1;
    static boolean[] visited;
    static List<Integer>[] list;
    
    public static void dfs(int x){
        visited[x] = true;
        for(int i=0; i<list[x].size(); i++){
            int now = list[x].get(i);
            if(visited[now]) continue;
            cnt++;
            dfs(now);
        }
    }
    
    public int solution(int n, int[][] wires) {
        int len = wires.length;
        
        for(int i=0; i<len; i++){
            list = new ArrayList[n+1];
            for(int k=0; k<n+1; k++){
                list[k] = new ArrayList<>();
            }
            cnt = 1;
            for(int j=0; j<len; j++){
                // i번째 송전탑 연결 무시
                if(i == j) continue;
                int x = wires[j][0];
                int y = wires[j][1];
                list[x].add(y);
                list[y].add(x);
            }
            visited = new boolean[n+1];
            // 아무 노드에서 시작
            dfs(1);
            // 두 전력망의 송전탑 차의 최솟값 갱신
            answer = Math.min(answer, Math.abs(n - 2 * cnt));
        }
        return answer;
    }
}