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

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

프로그래머스

2023-03-14

처음 접해보는 dfs유형의 문제였다. 그래프를 활용해서 모든 조건을 검사해봐야겠다라는 생각은 했지만 막상 코드로 적으려 해보니 무엇을 고려하고 어떻게 체크해야할지 알 수 없었다. 결국 괜찮은 풀이 방법을 찾아보고 참고해서 내가 알지 못한 것을 알아봤다.

참고 블로그:

https://isshosng.tistory.com/162

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

 

공부할 것을 적어보고 개선해서 다시한번 도전해야겠다.

 

import java.util.*;
class Solution {
    static ArrayList<Integer>[] graph;
    static int min;
    
    public int solution(int n, int[][] wires) {
        int answer = -1;
        
        // 3/14/2024
        // 공부할 것
        // dfs식 외우기
        // 그래프 자료구조
        // 분석해보기
        
        // 풀이방법 이해하기
        // 그래프 문제를 dfs로 풀이
        
        // 1. 그래프 초기화 <- 내가 알지 못한 방법
        // 2. 양방향 간선 추가 <- 내가 알지 못한방법
        // 3. 입력된 간선을 하나씩 제거하면서 그래프를 두개의 그룹으로 분리 <- 내가 알지 못한 방법
        // 4. dfs 함수
        
        // 1. 매개변수만큼의 graph 리스트 생성
        graph = new ArrayList[n + 1];
        min = Integer.MAX_VALUE;
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 2. 양방향 간선구조이므로 두번 add
        for(int i = 0; i < wires.length; i++) {
            int v1 = wires[i][0];  //노드 이름
            int v2 = wires[i][1];  //v1과 연결된 노드이름
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        
        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));
            min = Math.min(min, diff);
            
            // 그래프에서 다시 간선 추가
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        
        return min;
    }
        static int dfs(int v, boolean[] visited) {
            visited[v] = true;
            int cnt = 1;
            
            // graph[v]에 저장된 간선 정보들 체크
            for (int next: graph[v]) {
                if (!visited[next]) {
                    cnt += dfs(next, visited);
                }
            }
            return cnt;
        }
    
}