[플머] 전력망을 둘로 나누기 ⚡️ (Java)

문제 링크

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

프로그래머스

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

 

구조화

살짝 백준 양배추st
처음에 list에서 아예 삭제하고 넣고를 생각했지만 그냥 그거를 탐색 안하면 되잖아? 해서 int not 매개변수를 넘겨줘서 걔는 탐색안하도록 만듦
주석 부분이 삭제 후 추가하는 부분

소스 코드(배열 크기 변수로 저장 O)

import java.util.*;

class Solution {
    static int N;
    static boolean[] v;
    static List<Integer>[] list;
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        int w = wires.length;
        
        N = n;
        list = new List[n+1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < w; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            list[to].add(from);
            list[from].add(to);
        }
        
        for (int i = 0; i < w; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            int tCnt = bfs(to, from);
            int fCnt = bfs(from, t
            
            answer = Math.min(Math.abs(tCnt - fCnt), answer);
        }
        
        return answer;
    }
    
    static int bfs(int start, int not) {
        v = new boolean[N+1];
        v[start] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        int cnt = 1;
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            for (int i : list[cur]) {
                if (v[i] || i==not) continue;
                q.offer(i);
                v[i] = true;
                cnt++;
            }
        }
        
        return cnt;
    }
}

 

소스 코드(배열 크기 변수로 저장 X)

import java.util.*;

class Solution {
    static int N;
    static boolean[] v;
    static List<Integer>[] list;
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        
        N = n;
        list = new List[n+1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < wires.length; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            list[to].add(from);
            list[from].add(to);
        }
        
        for (int i = 0; i < wires.length; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            int tCnt = bfs(to, from);
            int fCnt = bfs(from, to);
            
            answer = Math.min(Math.abs(tCnt - fCnt), answer);
        }
        
        return answer;
    }
    
    static int bfs(int start, int not) {
        v = new boolean[N+1];
        v[start] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        int cnt = 1;
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            for (int i : list[cur]) {
                if (v[i] || i==not) continue;
                q.offer(i);
                v[i] = true;
                cnt++;
            }
        }
        
        return cnt;
    }
}

프로그래머스에서만 인지 모르겠는데
int w = wires.length;를 안하는 게 더 빠름

실패 코드

import java.util.*;

class Solution {
    static int N;
    static boolean[] v;
    static List<Integer>[] list;
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        int w = wires.length;
        N = n;
        list = new List[n+1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < w; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            list[to].add(from);
            list[from].add(to);
        }
        
        for (int i = 0; i < w; i++) {
            int to = wires[i][0];
            int from = wires[i][1];
            
            list[to].remove(from);
            list[from].remove(to);
            
            int tCnt = bfs(to);
            int fCnt = bfs(from);
            
            list[to].add(from);
            list[from].add(to);
            
            answer = Math.min(Math.abs(tCnt - fCnt), answer);
        }
        
        return answer;
    }
    
    static int bfs(int start) {
        v = new boolean[N+1];
        v[start] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        int cnt = 1;
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            for (int i : list[cur]) {
                if (v[i]) continue;
                q.offer(i);
                v[i] = true;
                cnt++;
            }
        }
        
        return cnt;
    }
}

삭제 후 추가하는 건 오류남