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

dfs를 사용해 풀었다. 

 

1. 1번 노드부터 dfs 실행. 방문한 노드는 다시 탐색하지 않는다.

2. 각 노드는 연결된 노드 중 방문하지 않은 노드들에 dfs 실행

3. 연결된 노드들에 대해 dfs가 끝난 노드는 자신을 포함해 dfs를 보낸 노드 수를 더한 값을 반환

ex) 예시 1번 기준 7번 노드에선 8, 9번 노드에 dfs를 실행하고 8, 9번은 각각 1을 반환
7번 노드에 대한 탐색이 끝났으면, 자기 자신을 포함해 3 반환.

4. 3번에서 반환된 값은 | (n - 반환 값) - 반환 값| 연산을 해 현재 답과 비교해 작은 것을 저장

5. 모든 노드의 탐색이 끝날 때 까지 2~4번 반복

 

이 결과가 끝날 때의 각 노드의 값들은 다음과 같다. (예시 1번 기준)

 

코드

import java.util.*;

class Solution {
    ArrayList<ArrayList<Integer>> tree = new ArrayList();
    int answer = 0x7FFFFFFF;
    boolean[] visit;
    public int solution(int n, int[][] wires) {
        visit = new boolean[n + 1];
        for(int i = 0; i <= n ; i++) {
            tree.add(new ArrayList());
        }

        for(int i = 0; i < wires.length; i++) {
            tree.get(wires[i][0]).add(wires[i][1]);
            tree.get(wires[i][1]).add(wires[i][0]);
        }
        dfs(n, 1);
        return answer;
    }

    public int dfs(int n, int index) {
        visit[index] = true;
        int ret = 0;
        int total = 1;  // 자기 자신도 셈
        for(int i=0; i<tree.get(index).size(); i++) {
            int element = tree.get(index).get(i);
            if(visit[element])
                continue;
            visit[element] = true;
            // 해당 노드에서의 하위 노드 탐색
            ret = dfs(n, element);
            answer = Math.min(answer, Math.abs((n - ret) - ret));
            total += ret;
        }
        return total;
    }
}

 

결과

 

문제 해결법은 빨리 생각했지만, 자꾸 다른 방법이 있지 않을까 고민하다 시간만 버렸다.

 

요즘 문제 풀 때 정석이 있는데도 다른 방식으로 풀려다 시간만 잡아먹는 일이 많아서 고민이다.