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

allzeroyou·2025년 1월 22일
0

Java-Algorithm

목록 보기
13/26
post-thumbnail

Sabrina Carpenter-Good Graces
문제 풀면서 들은 노래

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=java

문제 설명

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

송전탑 개수:n, 전선 정보: wires, 전선들 중 하나 끊어 송전탑 개수가 비슷해지도록 두 전력망을 나눌때, 두 전력망이 가지고 있는 송전탑 개수 차이(절댓값) return.

생각

2차원 배열인 wires를 어떤 자료구조를 사용해서 저장해야 문제 풀이가 쉬울까..
또, 이렇게 만든 자료구조에서 이어진 전선들 중 어떤 전선을 잘라야 두 전력망이 갖는 노드들의 개수가 비슷할까?..

풀이

그래프를 코드로 나타내는 2가지 방법이 있다.
1. 인접행렬, 2. 인접리스트인데, 간선의 수가 많으면 인접 행렬이 낫고, 간선의 수가 얼마 없을땐 인접리스트 사용이 유리.
해당 문제에서 n이 2이상 100 이하라고 했으니 희소그래프에 해당하므로, 인접리스트를 사용하자.

  1. 자료구조 선택
  • 인접리스트를 사용해 그래프(트리) 표현
  • HashMap<Integer, List<Integer>>를 사용해 각 노드와 연결된 노드 저장
  1. 알고리즘
  • 각 전선을 하나씩 제거해보고, 그때마다의 두 전력망의 크기 차이 계산
  • 연결 요소 개수의 계산이므로 bfs, dfs 상관없음. 편한대로 bfs 사용해서 풀겠음.

정답코드

import java.util.*;

class Solution {
    // 1. 인접리스트 생성
    HashMap<Integer, List<Integer>> map = new HashMap<>();
    
    public int solution(int n, int[][] wires) {
        int answer = -1;
        
        for(int[] wire : wires){
            map.putIfAbsent(wire[0], new ArrayList<>());
            map.putIfAbsent(wire[1], new ArrayList<>());
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]); // 양방향 그래프
        }
            
        // 2. 각 전선을 하나씩 제거해보고 두 전력망 크기 차이 계산
        int minDiff = n; // 크기 차이 최솟값        
        
        for(int[] wire: wires){
            // 전선 제거
            map.get(wire[0]).remove(Integer.valueOf(wire[1]));
            map.get(wire[1]).remove(Integer.valueOf(wire[0]));
            
            // bfs로 연결 개수 계산
            int size = bfs(wire[0], n);
            
            // 차이 계산
            int diff = Math.abs(n- 2*size); // |(n-size)-size|이므로
            minDiff = Math.min(diff, minDiff);
            
            // 전선 복구
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }
        
        return minDiff;
    }
     // 3. bfs
    private int bfs(int start, int n){
        Queue<Integer> q = new LinkedList<>(); // 큐 생성
        boolean[] visited = new boolean[n+1]; // 방문체크
        q.offer(start);
        visited[start]=true;
        
        int size = 0; // 크기
        
        while(!q.isEmpty()){
            int node = q.poll();
            size ++;
            
            // 연결 요소 구하기
            for(int nei: map.get(node)){
                if(!visited[nei]){
                    q.offer(nei);
                    visited[nei]=true;
                }
            }
        }
        return size;
    }
}

코드 주요 로직

1.인접리스트를 만들어서 전선들을 저장한다

  • 이때 양방향 그래프임에 주의

2. 하나씩 전선들을 제거해보며, 두 전력망 크기 차이의 최솟값을 구한다.

  • 하나씩 제거하며, 그래프 탐색 기법인 bfs를 사용해, 그때 전력망의 연결 요소를 구한다.
  • 전력망 차이 계산 후, 전선을 복구해 다른 전선을 잘랐을때가 최솟값인지 확인한다.

생각해볼 점

graph.get(wire[0]).remove(Integer.valueOf(wire[1]));
여기서 바로 remove(wire[1])을 안하고 Integer.valueOf를 붙여주는 이유?

  1. 타입 문제:
    remove() 메소드는 오버로딩되어 있어, 인자의 타입에 따라 다르게 동작합니다.
  • remove(int index)는 리스트의 특정 인덱스 요소를 제거합니다.
  • remove(Object o)는 리스트에서 특정 객체를 찾아 제거합니다.
  1. 의도한 동작:
    여기서는 특정 값을 가진 요소를 제거하려고 합니다.
    wire은 int 타입이므로, 그대로 사용하면 인덱스로 해석될 수 있습니다.

  2. 해결책:
    Integer.valueOf(wire) 는 int를 Integer 객체로 변환합니다.
    이렇게 하면 remove(Object o) 메소드가 호출되어 의도한 대로 특정 값을 가진 요소를 제거합니다.

예를 들어, wire이 3이고 리스트가 [1, 2, 3, 4]라면:
remove(3)은 인덱스 3의 요소(4)를 제거합니다.
remove(Integer.valueOf(3))은 값이 3인 요소를 제거합니다.
따라서 Integer.valueOf()를 사용하여 명시적으로 객체를 생성함으로써 의도한 대로 특정 값을 가진 요소를 제거.

BFS 기본 코드(java)

import java.util.*;

public class BFS {
    public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 6; // 노드의 수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        boolean[] visited = new boolean[n];
        bfs(0, graph, visited);
    }
}
profile
모든 건 zero 부터, 차근차근 헛둘헛둘

0개의 댓글