[JAVA] 전력망을 둘로 나누기

NoHae·2025년 1월 16일

코딩테스트

프로그래머스_코딩테스트

목록 보기

21/51

문제 출처

코딩테스트 연습 > 완전탐색 > 전력망을 둘로 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971

문제 설명

n개의 송전탑이 전선을 통해 하나의 "트리" 형태로 연결되어 있다. 이 전선들 중 하나를 끊어 네트워크를 2개로 분할한다.

송전탑의 개수 n, 전선 정보 2차원 배열 wires[][]가 주어질 때, 전선들 중 하나를 끊었을 때, 송전탑 개수가 가능한 비슷하도록 두 네트워크 송전탑 개수 차이(절대값)를 return 하라.

접근 방법

노드간의 인접상황을 알려주는 인접행렬 2차원 배열 arr 를 만들어 정보를 입력한다. 그리고 인접행렬을 끊어서 생기는 네트워크의 갯수를 bfs를 통해 계산후 다시 연결시켜준다.

bfs 함수 argument로 노드 전체의 갯수 n, 시작 노드 start를 받는다. 이후 방문여부 확인용 배열 visited를 만들고, 시작 노드를 큐에 삽입한다.

큐에 삽입한 시작 노드를 꺼내어 visited에 노드의 방문 표시를 해준 뒤, 방문하지 않은 노드를 제외하고, 해당 노드와 연결되어있는 노드를 arr에서 찾아 count를 1증가 시키고 큐에 삽입한다. 해당 과정으로 한 쪽 네트워크의 크기를 알 수 있다.

bfs가 끝나면 한 쪽 네트워크 값과 다른 쪽 네트워크의 절댓값을 return한다. 이 후 노드는 다시 연결해준다.

이를 모든 연결 된 노드에 반복작업하여 절댓값이 가장 작은 값을 return 한다.

import java.util.*;

class Solution {
    static int arr[][];
    
    public int bfs(int n, int start){
        int visited[] = new int[n+1];
        Queue<Integer> q = new LinkedList<>();
        int count = 1;
        q.offer(start);
        
        while(!q.isEmpty()){
            int point = q.poll();
            visited[point] =1;
            
            for(int i = 1; i<=n; i++){
                
            if(visited[i] == 1) continue;
            if(arr[point][i] == 1){
                count++;
                q.offer(i);
            }
        }
        }
        
        return Math.abs(n-count - count);

    }
    
    
    public int solution(int n, int[][] wires) {
        int answer = n;
         arr = new int[n+1][n+1];
        
        
        for(int i = 0; i<wires.length; i++){
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        
        for(int i = 0; i<wires.length; i++){
            int a = wires[i][0];
            int b = wires[i][1];
            
            arr[a][b] = 0;
            arr[b][a] = 0;
            
            answer = Math.min(answer, bfs(n,a));
            
            arr[a][b] = 1;
            arr[b][a] = 1;
        }
        
        
        return answer;
    }
}