LV2 - 전력망을 둘로 나누기 (Java)

 

---

 

문제

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

프로그래머스

 

풀이

진짜 단순한데 괜히 이상하게 생각했던 문제..

 

문제 설명 그대로, 간선을 제거한다음, dfs나 bfs를 수행해서 얼만큼의 노드를 방문했는지 계산하고 그 차가 가장 작은 값을 return 해주면 되는 문제이다.

 

그래서 처음에는 간선을 다 추가해주고,

wires 배열을 돌면서 간선 하나씩을 삭제한 다음

해당 간선에 연결된 두개의 노드 각각을 시작점으로 탐색을 시작하고,

몇 개의 노드를 방문했는지 기록한다음 두개의 차를 구하면 된다.

 

제한되는 수가 애초에 작기 때문에 왠만해서는 시간 초과는 안날 거 같은 문제다.

 

코드

import java.util.*;

class Solution {

    public ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
    public int answer = Integer.MAX_VALUE;

    public int solution(int n, int[][] wires) {

        // init ->  node 는 1부터 n 까지 존재.
        for (int i = 0; i < n + 1; i++) {
            arr.add(new ArrayList<>());
        }

        // 양방향 간선 추가
        for (int i = 0; i < wires.length; i++) {
            arr.get(wires[i][0]).add(wires[i][1]);
            arr.get(wires[i][1]).add(wires[i][0]);
        }

        for (int i = 0; i < wires.length; i++) {
            arr.get(wires[i][0]).remove((Integer) wires[i][1]);
            arr.get(wires[i][1]).remove((Integer) wires[i][0]);

            int n1 = bfs(new boolean[n + 1], wires[i][0], new ArrayDeque<>());
            int n2 = bfs(new boolean[n + 1], wires[i][1], new ArrayDeque<>());
            answer = Math.min(answer, Math.abs(n1 - n2));
            arr.get(wires[i][0]).add(wires[i][1]);
            arr.get(wires[i][1]).add(wires[i][0]);

        }
        return answer;
    }


    public int bfs(boolean[] visited, int node, Deque<Integer> deque) {
        deque.addLast(node);
        visited[node] = true;
        int cnt = 1;

        while (!deque.isEmpty()) {
            int value = deque.removeFirst();
            for (int val : arr.get(value)) {
                if (!visited[val]) {
                    visited[val] = true;
                    cnt++;
                    deque.addLast(val);
                }
            }
        }
        return cnt;
    }

}

 

후기

 

오랜만에 다시 할려니 머리가 엄청 굳었다... 열심히 풀어야겠다.