[프로그래머스/JAVA] 전력망을 둘로 나누기

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

프로그래머스

---

- 문제 풀이

1. 그래프 초기화

import java.util.*;

class Solution {
    static ArrayList<Integer>[] graph;
    static int min;
    
    // ... 생략
    graph = new ArrayList[n+1];
        min = Integer.MAX_VALUE; // 자바에서 표현할 수 있는 가장 큰 정수 값

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            // graph[1] = []
            // graph[2] = []
            // graph[3] = []
            // graph[4] = []
        }

 

 

 + 만약 ArrayList<Integer> graph = new ArrayList<>(); 형태로 작성하면,

이는 단일 ArrayList로 하나의 정점에만 연결된 값들을 저장하는 구조이다.

이 경우 전체 그래프를 표현하기보다는 하나의 정점과 그 정점에 연결된 인접 정점만 관리하는 용도로 사용됩니다.

 // 단일 정점에 연결된 인접 정점을 저장하는 리스트
        ArrayList<Integer> graph = new ArrayList<>();

        // 인접 정점 추가 (1번 정점에서 연결된 정점들)
        graph.add(2);
        graph.add(3);
        graph.add(5);

        // 결과 출력
        System.out.println(graph);
        
        // 결과
        // [2, 3, 5]

 

 

결과적으로 이 구조는 하나의 정점에 대한 정보만 포함하고 있어,

여러 정점을 관리하려면 ArrayList[] 배열이나 List<List<Integer>>와 같은 구조가 필요합니다.

 

 

 

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);
            // wires = [[1, 2], [2, 3], [3, 4]] 일때,
            // graph[1] = [2]
            // graph[2] = [1, 3]
            // graph[3] = [2, 4]
            // graph[4] = [3]
        }

 

 

 

 

3. 연결 정보를 하나씩 끊어서

 for (int i = 0; i < wires.length; i++) {
            int v1 = wires[i][0];
            int v2 = wires[i][1];


            // 전선을 끊음
            graph[v1].remove(Integer.valueOf(v2));
            graph[v2].remove(Integer.valueOf(v1));

 

문자열 -> 정수로 변환하려면,

(Integer.valueOf(), Integer.parseInt() 사용)

 

 

4. 끊어진 두 전력망 중 하나의 송전탑 개수들 세기

 // DFS로 한 전력망의 송전탑 개수 세기
		    boolean[] visited = new boolean[n+1];
            int cnt = dfs(1, visited);

 

 // 연결된 송전탑의 개수를 세는 함수
    static int dfs(int v, boolean[] visited) {
        // v: 현재 방문 중인 송전탑 번호
        visited[v] = true;
        int cnt = 1;

        for(int next : graph[v]) {
            if (!visited[next]) {
                cnt += dfs(next, visited);
            }
        }
        return cnt;
    }

 

 

 

5.  끊어진 두 전력망의 차이 구하기

  // 다른 전력망의 송전탑 개수는 n - cnt
            // Math.abs : 절댓값 구함
            int diff = Math.abs(cnt - (n - cnt));
            min = Math.min(min, diff);

            // 전선 복구
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        return min;

 

---

 

 

- 정답 코드

import java.util.*;

class Solution {
    static ArrayList<Integer>[] graph;
    static int min;

    // 연결된 송전탑의 개수를 세는 함수
    static int dfs(int v, boolean[] visited) {
        // v: 현재 방문 중인 송전탑 번호
        visited[v] = true;
        int cnt = 1;

        for(int next : graph[v]) {
            if (!visited[next]) {
                cnt += dfs(next, visited);
            }
        }
        return cnt;
    }

    public int solution(int n, int[][] wires) {
        // 1. 그래프 초기화
        graph = new ArrayList[n+1];
        min = Integer.MAX_VALUE; // 자바에서 표현할 수 있는 가장 큰 정수 값

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            // graph[1] = []
            // graph[2] = []
            // graph[3] = []
            // graph[4] = []
        }

        // 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);
            // wires = [[1, 2], [2, 3], [3, 4]] 일때,
            // graph[1] = [2]
            // graph[2] = [1, 3]
            // graph[3] = [2, 4]
            // graph[4] = [3]
        }

        // 3. 전선을 하나씩 끊어서 두 전력망의 송전탑 개수 차이 계산
        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));

            // DFS로 한 전력망의 송전탑 개수 세기
            int cnt = dfs(1, visited);

            // 다른 전력망의 송전탑 개수는 n - cnt
            // Math.abs : 절댓값 구함
            int diff = Math.abs(cnt - (n - cnt));
            min = Math.min(min, diff);

            // 전선 복구
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        return min;
    }
}