[Programmers] 전력망을 둘로 나누기

[문제 링크]

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

프로그래머스

 

[풀이 과정]

간선 하나씩 지운 그래프를 매번 dfs를 돌려 가장 작은 절댓값이 나오도록 구현하였습니다.

 

[코드]

import java.util.*;

class Solution {
    ArrayList<Integer>[] graph;
    boolean[] visited;
    int min;
    
    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n+1];
        min = Integer.MAX_VALUE;
        
        
        // graph 초기화
        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 s = wires[i][0];
            int e = wires[i][1];
            
            graph[s].remove(Integer.valueOf(e));
            graph[e].remove(Integer.valueOf(s));
            
            visited = new boolean[n+1];
        
            // 임의의 시작점 1
            int count = dfs(1);
            
            // dfs로 찾았던 연결 노드 수 - (전체 노드 - dfs로 찾았던 연결 노드 수)
            int diff = Math.abs(count - (n - count));
            
            min = Math.min(min, diff);
            
            graph[s].add(e);
            graph[e].add(s);
        }
        
        
        return min;
    }
    
    public int dfs(int node) {
        visited[node] = true;
        int c = 1;
        
        for(int g : graph[node]) {
            if(!visited[g]) {
                c += dfs(g);
            }
        }
        
        return c;
    }
}

[회고]

풀이 과정은 쉬웠지만 구현하는데 생각보다 많은 애를 먹었습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.