프로그래머스 lv2 - 전력망을 둘로 나누기 (자바)

문제

---

프로그래머스 lv2 - 전력망을 둘로 나누기

풀이

---

주어진 그래프를 코드로 나타낼 수 있는지가 중요한 문제

양방향 그래프 초기화 방법
(1) 인접 리스트
ArrayList를 배열로 선언

ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++)
    graph[i] = new ArrayList<>();

ArrayList를 2차원 ArrayList로 선언

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++)
    graph.add(new ArrayList<>());

편한 방식으로 선언하면 된다. ( 필자는 배열로 선언하는게 가독성이 더 좋다고 느껴졌음 )

(2) 인접 행렬

int[][] graph = new int[n + 1][n + 1];

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

전력망의 송전탑 개수를 구하는 방법
bfs or dfs 알고리즘을 사용하여 전체 개수를 구한다.
최소 거리를 구하는 게 아닌 전체 개수만 구하면 되므로 필자는 로직이 더 간단한 dfs를 사용하는 걸 추천한다.

어려웠던 점

---

처음 푼 코드가 Exception in thread "main" java.util.ConcurrentModificationException 에러 발생
로직 상 맞는 것 같은데 계속 에러가 나서 컴파일이 실패했다.
해당 에러는 컬렉션을 순회할 때 해당 컬렉션을 수정하면 주로 발생하는 에러이다. 참고

< 컴파일 에러로 실패한 코드 >

import java.util.*;
class Solution {
    int[] visited = new int[102];
    ArrayList<ArrayList<Integer>> a = new ArrayList<>(); // 송전탑 상태를 저장할 인접 리스트
    int answer = Integer.MAX_VALUE;
    public int solution(int n, int[][] wires) {
        for (int i = 0; i <= n; i++)
            a.add(new ArrayList<>());

        // 인접 리스트 초기 상태 세팅
        for (int i = 0; i < wires.length; i++) {
            int s = wires[i][0];
            int e = wires[i][1];
            a.get(s).add(e);
            a.get(e).add(s);
        }

        // 간선(n - 1개)들 중 한개 없애고 탐색  - max, min 구하기
        for (int i = 1; i <= n; i++) {
            Arrays.fill(visited, 0);
            for (int num : a.get(i)) { // 현재 송전탑에 연결되어 있는 간선을 1개씩 자르고 탐색
                a.get(i).remove(Integer.valueOf(num));
                a.get(num).remove(Integer.valueOf(i));

                answer = Math.max(answer, Math.abs(dfs(i) - dfs(num)));

                a.get(i).add(num);
                a.get(num).add(i);
            }
        }

        return answer;
    }

    int dfs(int num) {
        visited[num] = 1;
        int ret = 1;
        for (int next : a.get(num)) {
            if (visited[next] == 1) continue;
            ret += dfs(next);
        }
        return ret;
    }
}

이 코드의 문제점

1. 컬렉션을 순회할 때 순회하는 해당 컬렉션을 수정하여 ConcurrentModificationExceptio 에러 발생
2. 이미 삭제한 간선을 또 삭제
   -> 탑에 연결된 모든 간선을 하나씩 지운 후 dfs 돌리고 그 다음 탑으로 이동해서 이미 지운 간선을 또 지움

코드

---

< 인접 리스트와 dfs로 구현한 코드 >

import java.util.*;
class Solution {
    int answer = Integer.MAX_VALUE;
    ArrayList<Integer>[] graph;

    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n + 1]; // 인접 리스트
        for (int i = 1; i <= n; i++)
            graph[i] = new ArrayList<>();

        // 인접 리스트 초기 상태 세팅
        for (int i = 0; i < wires.length; i++) {
            int s = wires[i][0];
            int e = wires[i][1];
            graph[s].add(e);
            graph[e].add(s);
        }

        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);
            int diff = Math.abs(cnt - (n - cnt));
            answer = Math.min(answer, diff);

            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        return answer;
    }

    int dfs(int v, boolean[] visited) {
        visited[v] = true;
        int cnt = 1;
        for (int next : graph[v]) {
            if (visited[next]) continue;
            cnt += dfs(next, visited);
        }

        return cnt;
    }
}

< 인접 행렬과 bfs로 구현한 코드 >

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int[][] graph;

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

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

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

            answer = Math.min(answer, bfs(n, v1));

            graph[v1][v2] = 1;
            graph[v2][v1] = 1;

        }
        return answer;
    }

    int bfs(int n, int x){
        boolean[] visited = new boolean[n+1];
        int cnt = 1;

        Queue<Integer> q = new LinkedList<Integer>();
        visited[x] = true;
        q.add(x);        
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i = 1; i <= n; i++){
                if(graph[cur][i] == 1 && !visited[i]){
                    visited[i] = true;
                    q.add(i);
                    cnt++;
                }
            }
        }

        return (int)Math.abs(cnt - (n-cnt));
    }
}