99클럽 코테 스터디 36일차 전력망을 둘로 나누기

📝 문제

프로그래머스

🔥 시도해본 접근 방식

1. 모든 wire가 한번씩 끊어진 상황을 탐색하기 위한 반복문 선언

2. [1]의 반복문 안에서 끊어진 wire에 붙어있던 첫번째 송전탑을 기준삼아 송전탑에 연결되어 있는 송전탑의 개수를 dfs를 이용하여 구한다.

3. [2]에서 구한 연결된 송전탑 개수를 group1로 선언하고 group2는 전체 송전탑 - group1 으로 구한다.

4. group1과 group2의 차이를 answer와 비교하여 더 작은 값으로 초기화하도록 한다.

✨ 성공 코드

import java.util.Stack;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = n;

        // 전체 wire가 한번씩 끊어진 경우 순회
        for (int i = 0; i < wires.length; i++) {
            int[] cutWire = wires[i]; // 끊어진 wire

            // wire가 끊어진 송전탑과 연결된 송전탑을 찾아 stack에 넣을 때,
            // 중복 방지를 위한 플래그
            boolean[] linked = new boolean[n + 1];
            Stack<Integer> s = new Stack<>();

            // 첫 순회 송전탑 push
            s.push(cutWire[0]);
            linked[cutWire[0]] = true;

            int cnt = 0;

            while (!s.isEmpty()) {
                int top = s.pop();
                cnt++;

                // 끊어진 wire를 제외한 모든 wire 순회하며
                // 첫 순회 송전탑과 연결된 송전탑을 stack에 추가
                for (int j = 0; j < wires.length; j++) {
                    if (i == j) continue;

                    if (wires[j][0] == top && !linked[wires[j][1]]) {
                        s.push(wires[j][1]);
                        linked[wires[j][1]] = true;
                    } else if (wires[j][1] == top && !linked[wires[j][0]]) {
                        s.push(wires[j][0]);
                        linked[wires[j][0]] = true;
                    }
                }
            }

            int group1 = cnt;
            int group2 = Math.abs(n - cnt);

            answer = Math.min(answer, Math.abs(group1 - group2));
        }

        return answer;
    }
}