[99club/TIL] 4주차 - 수요일 TIL(Today I Learned)

항해99/99club1기TIL

[99club/TIL] 4주차 - 수요일 TIL(Today I Learned)

delay100 2024. 4. 17. 23:53

728x90

SMALL

안녕하세요. delay100 입니다.

미들러 문제. 전력망을 둘로 나누기

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

처음 풀 때 bfs문제인걸 파악하지 못했습니다.. 결국 답을 보고 나서야 해결했습니다.ㅠㅠ

예전에 bfs문제를 정말 많이 풀어봤다고 생각했는데도.. 문제를 보고도 못 알아본게 부끄럽네요..

import java.util.*;

class Solution {
    static boolean[] isVisited;
    static int[][] list;
    public int solution(int n, int[][] wires) {
        int answer = 101;
        list = new int[n][n];
        // 1. 인접 행렬 생성
        for(int i=0; i<(n-1); i++) {
            int x = wires[i][0] -1;
            int y = wires[i][1] -1;
            list[x][y] = list[y][x] = 1;
        }
        
        for(int i=0; i<(n-1); i++) {
            int x = wires[i][0] -1;
            int y = wires[i][1] -1;
            list[x][y] = list[y][x] = 0;
            isVisited = new boolean[n];
            // System.out.println("x= "+x+" /y= "+y);
            answer = Math.min(answer, bfs(x, n));
           
            list[x][y] = list[y][x] = 1;
        }
        
        return answer;
    }
    
    /**
    * @param start 탐색을 시작할 연결망
    * @param n 총 연결망 수
    * return 한 연결망 당 연결된 송전망 수
    */
    static int bfs(int start, int n) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        isVisited[start] = true;
        int cnt = 1;
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int i=0; i<n; i++) {
                if((!isVisited[i]) && (list[now][i]==1)) {
                    queue.offer(i);
                    isVisited[i] = true;
                    cnt++;
                }
            }
        }
        System.out.println("start= "+start+"/ cnt= "+cnt);
        return (int)Math.abs(cnt-(n-cnt));
    }
}