항해99 20일차 TIL( 전력망을 둘로 나누기 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

 

• 연결선이 가장 많은 숫자 구하기
• 그 숫자랑 연결되어 있는 선 하나씩 끊어보며 차이 업데이트하기

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {

        int group1N = 0;
        int group2N = 0;
        int[][] linesN = new int[n][2]; 
        int k = 1;
        
        //linesN = 숫자마다 연결되어 있는 숫자 개수 구하기
        for(int[] l : linesN) {
            l[0] = k;
            l[1] = 0;
            k++;
        }
        for(int i = 0; i < wires.length; i++ ) {
            linesN[wires[i][0]-1][1]++;
            linesN[wires[i][1]-1][1]++;
        }
        
        //가장 많이 연결되어 있는 숫자 찾기
        Arrays.sort(linesN, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        
        int maxConnectionNumber = linesN[0][0];
        int maxConnection = linesN[0][1];
        boolean visited[] = new boolean[n];
        int[] cutIndex = new int[maxConnection];
        
        //가장 많이 연결되어 있는 숫자가 들어잇는 wires 인덱스 찾기
        int cutIndexPlus = 0;
        for(int i =0; i < wires.length; i++) {
                if(wires[i][0] == maxConnectionNumber || wires[i][1] == maxConnectionNumber) {
                    cutIndex[cutIndexPlus] = i;
                    cutIndexPlus++;
                }
        }
        
        //하나 씩 가장 많이 연결되어 있는 숫자가 들어잇는 인덱스 없애면서 wires 탐색하며 그룹마다 연결 개수 확인
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        int min = Integer.MAX_VALUE;
        for(int i =0; i < cutIndex.length; i++) {
            visited[cutIndex[i]] = true;
            for(int j =0; j < wires.length; j++) {
                if(visited[j] == false) {
                    if(set1.isEmpty()) {
                        set1.add(wires[j][0]);
                        set1.add(wires[j][1]);
                    }
                    else{
                        if(set1.contains(wires[j][0]) || set1.contains(wires[j][1])) {
                            set1.add(wires[j][0]);
                            set1.add(wires[j][1]);
                        }
                        else{
                            set2.add(wires[j][0]);
                            set2.add(wires[j][1]);
                        }
                    }
                }
            }
            min = Math.min(min, Math.abs(set1.size() - set2.size()));
            visited[cutIndex[i]] = false;
        }
        
        return  min;
    }
}

위에 알고리즘 설명은 두 줄로 끝인데 저 말은 구현하려다보니 코드가 되게 길어졌다.
테스트 실패도 실패지만 문제 난이도를 봐서는 절대 이 코드의 길이가 나오면 안된다 싶다. 짜면서도 아 ~ 산으로 가고 있구나 하면서도 내 구현능력을 테스트 해보고 싶어 끝까지 작성했다.

 

디버깅하는 법을 몰라 System.out.println으로 값을 찍어봤다.

2 번째 시도  

• maxConneciontNumber가 포함되고 선을 잘라야 하는 인덱스에서 maxConneciontNumber아닌 숫자를 다른 set에 못 넣고 있다.
• cutIndex : 1일 때를 보면 cutIndex:1이 포함이 안되긴 했지만, {3,4}가 포함되어 set1 번에 {1,2,3,4}가 포함되어있는 거를 확인할 수 있다. 

 

• set1,set2가 반복문을 돌 때 초기화가 되지 않았다.
  • set1,set2 선언을 반복문 안에 넣는다.
• 선이 잘린 인덱스를 포함(visited[i] == true) 하는 가정문을 추가해준다.

결과 테스트케이스 3개가 통과해 돌려보았지만 제출테스트에서는 2개밖에 성공하지 못했다.

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {

        int group1N = 0;
        int group2N = 0;
        int[][] linesN = new int[n][2]; 
        int k = 1;
        
        //linesN = 숫자마다 연결되어 있는 숫자 개수 구하기
        for(int[] l : linesN) {
            l[0] = k;
            l[1] = 0;
            k++;
        }
        for(int i = 0; i < wires.length; i++ ) {
            linesN[wires[i][0]-1][1]++;
            linesN[wires[i][1]-1][1]++;
        }
        
        //가장 많이 연결되어 있는 숫자 찾기
        Arrays.sort(linesN, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        
        int maxConnectionNumber = linesN[0][0];
        int maxConnection = linesN[0][1];
        boolean visited[] = new boolean[n];
        int[] cutIndex = new int[maxConnection];
        
        //가장 많이 연결되어 있는 숫자가 들어잇는 wires 인덱스 찾기
        int cutIndexPlus = 0;
        for(int i =0; i < wires.length; i++) {
                if(wires[i][0] == maxConnectionNumber || wires[i][1] == maxConnectionNumber) {
                    cutIndex[cutIndexPlus] = i;
                    cutIndexPlus++;
                }
        }
        // System.out.println("maxConnectionNumber: " + maxConnectionNumber);
        // for(int i: cutIndex) {
        //     // System.out.println("cutIndex: " + i);
        // }
        
        //하나 씩 가장 많이 연결되어 있는 숫자가 들어잇는 인덱스 없애면서 wires 탐색하며 그룹마다 연결 개수 확인
       
        int min = Integer.MAX_VALUE;
        for(int i =0; i < cutIndex.length; i++) {
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            visited[cutIndex[i]] = true;
            for(int j =0; j < wires.length; j++) {
                if(visited[j] == false) {
                    if(set1.isEmpty()) {
                        set1.add(wires[j][0]);
                        set1.add(wires[j][1]);
                        // System.out.println("set1.isEmpty()");
                    }
                    else{
                        if(set1.contains(wires[j][0]) || set1.contains(wires[j][1])) {
                            set1.add(wires[j][0]);
                            set1.add(wires[j][1]);
                            // System.out.println("set1.contains(wires[j][0]) || set1.contains(wires[j][1])");

                        }
                        else{
                            // System.out.println("set1.contains(wires[j][0]) || set1.contains(wires[j][1]) else");
                            set2.add(wires[j][0]);
                            set2.add(wires[j][1]);
                        }
                    }
                    // System.out.println("Set1: " + set1);
                    // System.out.println("Set2: " + set2);
                } 
                else {
                    if(wires[j][0] == maxConnectionNumber){
                        set2.add(wires[j][1]);
                    }
                    else {
                         set2.add(wires[j][0]);
                    }
                }
            }
            // System.out.println("final Set1: " + set1);
            // System.out.println("final Set2: " + set2);

            min = Math.min(min, Math.abs(set1.size() - set2.size()));
            visited[cutIndex[i]] = false;
        }
        
        return  min;
    }
}

3 번째 시도   

이 망가진 코드를 어떻게든 수정해보려고 했지만, 접근법부터 틀렸다는 것을 깨달았습니다. 연결이 가장 많이 되어있는 노드의 선을 잘라도 정답이 아닐 수도 있다는 거입니다. 

 

도저히 유지보수가 힘들어 다른 사람들의 코드를 보며 공부해봤습니다.

• 노드의 관계를 인접리스트를 활용한다.
• 인접리스트에서 하나씩 삭제해가며 탐색해보며 최솟값을 업데이트한다.
• 탐색은 dfs로 구현한다.

import java.util.ArrayList;
 
class Solution {
    static ArrayList<Integer>[] graph;
    static int min;
 
    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n + 1];
        min = Integer.MAX_VALUE;
 
        // 그래프 ArrayList 초기화. 노드 개수만큼 ArrayList 생성
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
 
        // 양방향 간선 구조이므로 두 번 add를 해준다
        for (int i = 0; i < wires.length; i++) {
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
 
        for (int i = 0; i < wires.length; i++) {
            int v1 = wires[i][0];
            int v2 = wires[i][1];
 
            boolean[] visited = new boolean[n + 1];
 
            // 해당 간선을 그래프에서 제거
            graph[v1].remove(Integer.valueOf(v2));
            graph[v2].remove(Integer.valueOf(v1));
 
            int cnt = dfs(1, visited); // 임의의 시작점에서 dfs 탐색
 
            int diff = Math.abs(cnt - (n - cnt));
            min = Math.min(min, diff);
 
            // 그래프에 다시 간선 추가
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
 
        return min;
    }
 
    static int dfs(int v, boolean[] visited) {
        visited[v] = true;
        int cnt = 1;
 
        for (int next : graph[v]) {
            if (!visited[next]) {
                cnt += dfs(next, visited);
            }
        }
 
        return cnt;
    }
}