[ TIL - PGS ] 99클럽 코테 스터디 36일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• 완전탐색

 

✅ 오늘 공부한 내용

• 오늘의 프로그래머스 파일! 전력망을 둘로 나누기

프로그래머스

 

 

👀 오늘의 회고

🔥 어떤 시도를 했는가?

• 오늘의 풀이

import java.util.*;

class Solution {
    // 송전탑 간의 연결을 저장할 그래프
    List<Integer>[] graph;
    
    public int solution(int n, int[][] wires) {
        // 그래프 초기화
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 그래프에 송전탑 연결 정보 추가
        for (int[] wire : wires) {
            int v1 = wire[0];
            int v2 = wire[1];
            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        int minDifference = Integer.MAX_VALUE;

        // 각 전선을 끊어보면서 두 네트워크의 송전탑 개수 차이를 계산
        for (int[] wire : wires) {
            int v1 = wire[0];
            int v2 = wire[1];

            // 전선을 끊음
            graph[v1].remove((Integer) v2);
            graph[v2].remove((Integer) v1);

            // 끊어진 상태에서 각 네트워크의 송전탑 개수를 구함
            int sizeOfSubNetwork = bfs(v1, n);
            int difference = Math.abs(sizeOfSubNetwork - (n - sizeOfSubNetwork));

            // 최소 차이를 갱신
            minDifference = Math.min(minDifference, difference);

            // 전선을 다시 연결
            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        return minDifference;
    }

    // BFS로 송전탑 개수를 셈
    private int bfs(int start, int n) {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        int count = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;

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

        return count;
    }
}

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해99문제 풀기
• 리드미 및 main 브렌치에 합치기...
• 원티드 인턴쉽 수업 듣기
• 책읽기