과제 진행하기

2023.07.19 (WED)

---

문제 : 프로그래머스 - LV2. 전력망을 둘로 나누기

---

접근법

조건 및 설명

1. n개의 송전탑이 하나의 트리 형태로 연결
2. 전선들 중 하나를 끊어서, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.
3. 두 전력망의 송전탑 개수의 차이를 return

해결법

1. 모두 탐색을 해도 되는 문제기 때문에, BFS를 사용한다.
2. 매번 가장 작은 값을 저장한다.
3. 자른 기준으로, 두 개의 노드를 탐색하여 갯수를 센다.

결과 코드

import java.util.*;

class Solution {

    public int solution(int n, int[][] wires) {
        int answer = -1;
        public static boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i ++) {

        }

        return answer;
    }

    public static int bfs(int start, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        // current node visited
        visited[start] = true;

        while(!q.isEmpty()) {
            int x = q.poll();

            for (int i = 0; i < visited.length; i++) {
                // ...
            }
        }
    }
}