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

안녕하세요. delay100 입니다. 

---

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

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

프로그래머스

처음 풀 때 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));
    }
}

---

+ 비기너 문제

내적 (https://school.programmers.co.kr/learn/courses/30/lessons/70128)

프로그래머스

+ 챌린저 문제

미로 탈출 명령어 (https://school.programmers.co.kr/learn/courses/30/lessons/150365)

프로그래머스

---

감사합니다. 피드백 환영합니다.