99클럽 코테 스터디 10일차 TIL: [프로그래머스] 전력망을 둘로 나누기

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

프로그래머스

 

• 전선들 중 하나를 골라 끊어야 한다. 따라서 wires를 하나씩 고르며 완전탐색을 진행했다.
• 그리고 끊은 전선을 기준으로 dfs를 진행한다. 예를 들어, 3과 4를 이은 전선을 끊을 경우 3을 기준으로 이어진 송전탑들이 몇 개인지 dfs를 진행하고, 4를 기준으로 이어진 송전탑들이 몇 개인지 dfs를 진행한다. 그리고 두 값의 차이를 구한다.
• 내가 유독 헷갈렸던 부분은 dfs에서 sum에 값을 더하고 sum을 return하는 부분이다. 매번 반환값이 없는 재귀함수만 사용하다가 int를 반환하려고 하니 잘 와닿지 않는 거 같다. 이런 류의 문제를 좀 더 풀어봐야겠다!

class Solution {
    
    int n;
    int[][] wires;
    int answer = Integer.MAX_VALUE;
    boolean[] visited;
    boolean[][] map;
    
    public int solution(int n, int[][] wires) {
        this.n = n;
        this.wires = wires;
        
        for (int i = 0; i < n - 1; i++) {
            visited = new boolean[n + 1];
            map = new boolean[n + 1][n + 1];
            
            for (int j = 0; j < n - 1; j++) {
                if (i == j) continue;
                map[wires[j][0]][wires[j][1]] = true;
                map[wires[j][1]][wires[j][0]] = true;
            }
            
            int result1 = dfs(wires[i][0]);
            int result2 = n - result1;
            answer = Math.min(answer, Math.abs(result1 - result2));
        }
        return answer;
    }
    
    public int dfs(int start) {
        visited[start] = true;
        int sum = 1;
        
        for (int i = 1; i <= n; i++) {
            if (map[start][i] && !visited[i]) {
                sum += dfs(i);
            }
        }
        
        return sum;
    }
}