[알고리즘/Programmers] LV2. 전력망을 둘로 나누기 (Java)

 

오늘의 학습 키워드

• DFS

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

import java.util.ArrayList;

public class test_86971_X {

    static ArrayList<Integer>[] graph;
    static int min;

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

    public static int solution (int n, int[][] wires) {
        graph = new ArrayList[n+1];
        min = n;

        // 1. ArrayList 초기화
        for(int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 2. 양방향 그래프 초기화
        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);
        }

        // 3. 간선 하나씩 빼면서 dfs 돌리기
        for(int i=0; i<wires.length; i++) {
            boolean[] visited = new boolean[n+1]; // 방문 노드 기록

            // 간선 빼기
            int removeV1 = wires[i][0];
            int removeV2 = wires[i][1];
            graph[removeV1].remove(Integer.valueOf(removeV2));
            graph[removeV2].remove(Integer.valueOf(removeV1));

            int cnt = dfs(1,visited);

            int diff = Math.abs(cnt-(n-cnt));
            min = Math.min(diff, min);

            // 간선 다시 넣기 (다음 포문에서 삭제한 간선 사용 할 수 있도록)
            graph[removeV1].add(removeV2);
            graph[removeV2].add(removeV1);
        }

        return min;
    }

    public 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); // 방문할때마다 cnt(1)씩 증가
            }
        }
        return cnt;
    }
}

• 양방향 그래프를 초기화한다.
• 간선을 하나씩 빼서 그래프를 2개로 나눈다. 간선을 하나 뺀 그래프로 dfs를 돌리면서 나뉜 두 그래프 중 한 그래프의 노드 개수를 알아내어, 차이를 계산하고, 차이의 최소값을 구한다.
• 최소값을 찾은 후 뺀 간선을 다시 넣어줘야 루프 다시 돌 때 뺐던 간선을 포함시켜 계산할 수 있다. 빠뜨리지 않기!

3. 피드백

• 다른 코드를 참고하여 이해했지만 스스로 풀어내지 못했다.
• 두 그래프를 어떻게 쪼개서 계산하지? 막막했는데 풀이보니까 아하..

4. 새로 알게된 것

• List에 remove 오버로딩 함수가 두개이다. 그래서 필요에 따라 잘 사용해야 한다.
  • remove(int index) : 지정된 위치에 있는 요소를 제거
  • remove(O object) : 지정된 객체와 일치하는 첫 번째 요소를 제거 -> 해당 풀이의 경우, 값을 찾아 제거해야 하기 때문에 객체형으로 삭제해야 원하는 결과를 얻을 수 있다.

graph[removeV1].remove(Integer.valueOf(removeV2));
graph[removeV2].remove(Integer.valueOf(removeV1));

 

참고

https://isshosng.tistory.com/162