[프로그래머스/Lv. 2] 전력망을 둘로 나누기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int n;
    static int[][] wires;
    
    static ArrayList<Integer>[] A;   // 인접 리스트
    static boolean[] visited;        // 방문 배열
    static int min = Integer.MAX_VALUE;    // 트리의 최소 크기
    
    public int solution(int n, int[][] wires) { // 송전탑 개수, 전선정보
        this.n = n;
        this.wires = wires;
        
        A = new ArrayList[n + 1];
        for(int i = 1 ; i <= n ; i++) A[i] = new ArrayList<>();
        
        // 양방향 간선
        for(int i = 0 ; i < wires.length ; i++) {
            int a = wires[i][0];
            int b = wires[i][1];
            A[a].add(b);
            A[b].add(a);
        }
        
        // 🔔 모든 간선에 대해 한 번씩 끊어봄 (완전탐색)
        for(int i = 0 ; i < wires.length ; i++) {
            int a = wires[i][0];
            int b = wires[i][1];
            
            visited = new boolean[n + 1];    // 💥 반복문 돌 때마다 매번 새롭게 선언해줘야 함
            
            // 1. 해당 간선을 그래프에서 제거
            A[a].remove(Integer.valueOf(b));
            A[b].remove(Integer.valueOf(a));
            
            int cnt = dfs(1);   // 2. 임의의 시작점에서 dfs 탐색하며 각 그룹의 노드 개수 계산
            
            int diff = Math.abs(cnt - (n - cnt));   // 3. |송전탑 개수 차이| 계산
            min = Math.min(min, diff);              // 4. 최솟값 갱신
            
            // 5. 그래프에 다시 간선 추가
            A[a].add(b);
            A[b].add(a);
        }
        
        return min;
    }
    
    static int dfs(int v) {
        visited[v] = true;
        int cnt = 1;    // 노드 세는 변수 초기화
        
        for(int next : A[v]) {
            if(!visited[next]) {    // 방문하지 않은 인접 노드 방문하며 cnt 업데이트
                cnt += dfs(next);
            }
        }
        
        return cnt;
        
    }
}

 

 

🧩  해결 아이디어

• DFS

- 인접 행렬/리스트를 만든다.

- wires의 길이만큼 반복문을 돌며, wires[i]번째 원소를 제거한 모든 경우의 수를 탐색한다. (완전탐색)

 

 

---

🔺 다른 풀이들

- 완전탐색 부분이 조금 다르다. dfs 함수 인자로 (1, wires[i][0], wires[i][1]) 값을 가져가심

[프로그래머스] Level2 전력망을 둘로 나누기 (Java)

 

 

- 인접 리스트 대신 2차원 인접행렬 사용하셨고, BFS로 푸셨다. 이게 복습하기 좋은듯!

[프로그래머스]level 2: 전력망 둘로 나누기_Java(위클리 9주차)

프로그래머스 전력망을 둘로 나누기(JAVA)

---

💬 느낀 점

dfs나 bfs 써야겠단 생각은 했는데

간선 하나씩 다 끊어보면서 최솟값 구할 생각을 놓쳐서

다른 분 코드 참고해서 작성했다.

(어쩐지 숫자가 작더라니..!)

 

다음엔 꼭 혼자 힘으로 풀어보는 걸로...

 

1회독	2회독	3회독	4회독	5회독
V	240223

 

 

(+ 240223 2회독)

 BFS로 풀어보았다....

요 문제는 dfs가 좀 더 빠른듯..

→ 시간 복잡도 :  O(E * (V + E))

(E : wires의 길이)

import java.util.*;
 
class Solution {
    static int n;
    static int[][] wires;
    
    static List<Integer>[] A;
    static boolean[] visited;
    
    static int diff = Integer.MAX_VALUE;
    
    public int solution(int n, int[][] wires) { // 송전탑 수, 전선 정보
        this.n = n;
        this.wires = wires;
        
        A = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++) {
            A[i] = new ArrayList<>();
        }
        
        for(int[] w : wires) {
            A[w[0]].add(w[1]);
            A[w[1]].add(w[0]);
        }
        
        // 전선들 중 "하나" 끊어서 송전탑 개수가 가능한 비슷하도록
        for(int[] w : wires) {   
            visited = new boolean[n + 1];
            
            // 1. 전선줄 하나 끊어보기
            A[w[0]].remove(Integer.valueOf(w[1]));
            A[w[1]].remove(Integer.valueOf(w[0]));
            
            // 2. 두 전력망이 가진 송전탑 개수 차이 계산하기
            int cnt = bfs(1);   // 임의의 시작점에서 bfs
            diff = Math.min(diff, Math.abs(cnt - (n-cnt)));
            
            // 3. 전선줄 원상복구
            A[w[0]].add(w[1]);
            A[w[1]].add(w[0]);            
        }       
        
        return diff;
    }
    
    private static int bfs(int num) {
        int cnt = 1;
        visited[num] = true;
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(num);       
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
}

 

 

---

(참고)

[프로그래머스/자바] 전력망을 둘로 나누기 - bfs