[프로그래머스] lv.2 전력망을 둘로 나누기

Source Code : https://github.com/JangAJang/Algorithm/blob/main/프로그래머스_Lv2/전력망을%20둘로%20나누기/src/Solution.java

 

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

프로그래머스

문제의 링크는 여기 있다. 

 

완전탐색의 문제였지만, 완전탐색 하나만 생각해서 풀지 않았던 것 같다. 

완전탐색으로 각 경우에 탐색할 때, dfs를 사용했으니 틀린말은 아니겠지...??

 

일단, 문제를 어떻게 풀지를 생각했다. 

• 양방향 그래프의 구조를 HashMap<Integer, Set<Integer>>의 구조로 저장한다.
  시작점을 key, 도착점들을 Set<Integer>에 추가하는 식으로 만들었다. 
• 각 케이스마다 깊이 우선 탐색을 실행한다. 이 때, 파라미터로 Map형식의 그래프와, int[]형식의 스킵해야 할 점을 받았다. 
  • boolean[]타입의 방문내역을 생성했다. 길이는 HashMap.keySet의 길이로 받았다. 
  • 스택에 1번점을 넣었다. 1번이 끊어지면 결국 1, n-1개의 연결이 만들어지는 것이니까. 
  • 스택을 이용해 dfs를 구현했다. 
    • 스택의 마지막을 pop한다. 
    • 마지막 점을 key로 HashMap.get해주어, 연결된 점들의 주소를 받아온다. 
    • 연결된 점들에 대해 반복문을 수행한다. 
      • 만약 방문한 적이 없고, 스킵해야 하는 연결이 아니라면 아래의 사항을 수행한다. 
        
        • 스택에 값을 추가한다. 
        • 해당 주소의 방문여부를 true로 초기화한다. (visited[index] = true;)
  • 방문내역에서 참인 개수를 반환한다. 
• 반환한 값을 x라고 가정하고, 문제에서 총 점의 개수는 n으로 주었다. 이 때, 결국 두 전력망 사이의 차이는
  x - (n-x)이므로, n - 2 * x를 구한다. 
• 이 값들의 최소값을 반환한다. 

+ 스킵여부를 확인하는 방법은, 현재점과 다음점, 스킵해야 하는 연결을 입력받아

현재점 == 스킵연결[0] && 다음점 == 스킵연결[1] 이거나

현재점 == 스킵연결[1] && 다음점 == 스킵연결[0] 이면

참을 반환하게 했다. 

 

이렇게 아이디어를 짜두고, 구현을 시작했다. 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int result = Integer.MAX_VALUE;
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for(int index = 1; index <=n; index++){
            map.put(index, new HashSet<>());
        }
        for(int[] wire : wires){
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }
        for(int[] wire : wires){
            result = Math.min(result, Math.abs(n - 2 * countNode(map, wire)));
        }
        return result;
    }

    private int countNode(HashMap<Integer, Set<Integer>> map, int[] wire){
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[map.keySet().size()+1];
        stack.add(1);
        while(!stack.isEmpty()){
            int current = stack.pop();
            visited[current] = true;
            for(int next : map.get(current)){
                if(!visited[next] && !isSkip(wire, current, next)){
                    stack.push(next);
                    visited[next] = true;
                }
            }
        }
        int result = 0;
        for(boolean visit : visited){
            if(visit) result++;
        }
        return result;
    }

    private boolean isSkip(int[] wire, int current, int next) {
        return (wire[0] == current && wire[1] == next) ||
                (wire[1] == current && wire[0] == next);
    }
}

이렇게 코드를 만들었고, 이걸 리펙토링 하기로 했다. (메서드를 최대한 분리하기 위해서)

import java.util.*;

class Solution {

    private HashMap<Integer, Set<Integer>> map;

    public int solution(int n, int[][] wires) {
        createGraph(n,wires);
        int result = Integer.MAX_VALUE;
        for(int[] wire : wires){
            result = Math.min(result, Math.abs(n - 2 * countNode(wire)));
        }
        return result;
    }

    private void createGraph(int n, int[][] wires){
        map = new HashMap<>();
        for(int index = 1; index <=n; index++){
            map.put(index, new HashSet<>());
        }
        for(int[] wire : wires){
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }
    }

    private int countNode(int[] wire){
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[map.keySet().size()+1];
        stack.add(1);
        while(!stack.isEmpty()){
            int current = stack.pop();
            addNextStations(wire, current, visited, stack);
            visited[current] = true;
        }
        return countVisits(visited);
    }

    private int countVisits(boolean[] visited){
        int result = 0;
        for(boolean visit : visited){
            if(visit) result++;
        }
        return result;
    }

    private void addNextStations(int[] wire, int current, boolean[] visited, Stack<Integer> stack){
        for(int next : map.get(current)){
            if(!visited[next] && !isSkip(wire, new int[]{current, next})){
                stack.push(next);
                visited[next] = true;
            }
        }
    }

    private boolean isSkip(int[] wire, int[] currentWire) {
        return (wire[0] == currentWire[0] && wire[1] == currentWire[1]) ||
                (wire[1] == currentWire[0] && wire[0] == currentWire[1]);
    }
}

indent 2 이하로 최대한 기능들을 분리해 리펙토링까지 마무리했다. 

성공적.