<2252번 줄 세우기>

N명의 학생들을 키 순서대로 줄을 세우려고 한다.
각 학생의 키를 직접 재서 정렬하면 좋지만 키를 재지 못한다.
두 학생의 키를 비교하는 방법으로 정렬을 한다.
모든 학생들을 다 비교해 본 것이 아니라 일부 학생들의 키만들 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어진다.
줄을 세우는 프로그램을 작성해라.

<자료구조>

N: 학생의 수 -> 2^51e3 -> 정수 자료혐
M: 키를 비교한 횟수 -> 1e6 -> 정수 자료형
A,B: 두 학생의 번호 -> 번호는 1~2^51e3이고 A가 B의 앞에 서야 한다.

키가 작은 학생앞에 올 수 있는 학생 수를 기록할 수 있는 배열: int[]
키가 큰 학생의 뒤로 올 수 있는 학생을 저장하는 인접리스트: ArrayList

<알고리즘>

N명의 학생들을 M번 비교한 정보가 주어진다.
키를 비교한 결과는 선형이며 순환하지 않는다. -> 사이클이 없고, 방향성에 거스르지 않도록 순서가 형성된다.
학생들을 앞에서부터 줄을 세운다.
여러 가지 경우가 있을 경우 아무거나 출력한다.

키가 작은 학생의 앞의 학생수(진입차수)를 기록하여 가장 키가 큰학생(진입차수가 0인 학생)이 앞에 오도록 탐색을 한다.
최초에 본인보다 키가 큰학생이 없는 학생을 큐에 넣고 뒤로 오는 학생보다 앞에올 수 있는 학생 수(진입차수)를 감소시킨다.
그렇게 탐색을 진행하면서 키가 큰 학생들이 빠지면서 키가 작은 학생의 진입차수가 0이 되면(남아있는 학생들 중에서 키가 가장 커지면) q에 넣어준다.

q에 들어간 순서는 graph의 리스트 정렬 순서에 따라 달라 질 수 있고, 선후관계는 보장된다.

<시간 복잡도>

인접 리스트로 진출할(키가 작은 학생)을 그래프로 표현하여 시간복잡도가 O(E+V)로 32,000+100,000 시간 여유가 있다.

<공간 복잡도>

25681024*1024 bit 제한

• 32 bit : 정점의 개수를 저장하는 정수 자료형
• 32 bit : 간선의 개수를 저장하는 정수 자료형
• 32*1000 + 100000 bit: 다음에 올 수 있는 학생을 저장하는 인접 리스트
• 32(321000) bit: 정수 자료형을 담는 큐( 키가 가장 큰 학생들을 순서대로 담는 큐, 연결리스트로 구현되어 크기 가변)
• 32(321000+100000) bit: 결과를 담는 리스트
  제한보다 작은 값을 가짐으로 가능하다.

<어려웠던 점>

문제에서 학생의 키를 정점으로 사용하고, 비교하여 얻은 선후관계를 방향으로 하는 그래프까지는 유추가 되었다.
하지만 가장 먼저오는 학생을 지정할 수 있는 방법이 떠오르지 않았다. 앞에서 구현이 막혔음으로 당연하게 다음으로 올 수 있는 학생을 구현하지 못했다.
따라서, 위상정렬을 큐로 구현하는 일반적인 방법을 참고했다.
위상정렬은 순서가 있고, 순환하지 않는 그래프의 형태를 보인다. 문제에서 순환하지 않음을 확인하고 방향성을 유지하는 정렬을 원한다면 위상정렬을 고려할 필요가 있다.
또한, 인접리스트와 큐를 활용하여 구현할 경우 시간 복잡도 또한 BFS와 동일함으로 문제에서 위의 특징으로 구분해서 알고리즘을 선정해야한다.

다음으로 올 수 있는 노드를 저장하는 그래프와 앞에 올 수 있는0(즉, 진입할 수 있는) 노드의 개수를 저장하는 배열을 활용하여 순서를 보장하여 정렬을 하는 방법을 기억하고 활용하자.

해결 코드

import java.io.*;
import java.util.*;

public class Main{
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();
    static int[] inDegree;
    static ArrayList<ArrayList<Integer>> listGraph;
    static int N;
    static int M;

    static void input(){
        N = scan.nextInt();
        M = scan.nextInt();
        listGraph = new ArrayList<ArrayList<Integer>>();
        int i;
        for(i=0;i<N+1;i++) listGraph.add(new ArrayList<Integer>());
        inDegree = new int[N+1];
        int a,b;
        for(i=0; i<M; i++){
            a = scan.nextInt();
            b = scan.nextInt();
            listGraph.get(a).add(b);
            inDegree[b]++;
        }
    }
    static void topologySort(){
        ArrayList<Integer> result = new ArrayList<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=1;i<N+1;i++)
            if(inDegree[i]==0) q.offer(i);

        while(!q.isEmpty()){
            int cur = q.poll();
            result.add(cur);
            for(int nxt: listGraph.get(cur)){
                inDegree[nxt]--;
                if(inDegree[nxt]==0) q.offer(nxt);
            }
        }

        for(int i: result) sb.append(i).append(' ');
        System.out.println(sb);
    }

    static void pro(){
        topologySort();
    }

    public static void main(String[] args){
        input();
        pro();
    }

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;

        FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null||!st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
    }
}

<11725번 트리의 부모 찾기>

<문제 설명>

루트가 없는 트리가 주어진다.
트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성해라.
노드의 개수는 2에서 10만개이다.
트리 상에 연결된 두 정점의 정보가 주어진다.

<접근 방법>

루트가 없는 트리 정보가 주어지고, 트리의 루트를 1이라고 정했을 대의 각 노드의 부모를 구해야 하므로
1번 노드로 부터 탐색을 시작하면 연결된 노드들은 자식노드일 것이다.

i번째 노드에서 연결된 노드를 탐색할 때 BFS혹은 DFS 방식으로 탐색할 수 있다.
bfs로 구현하여 풀었다.

<공간 복잡도>

인접행렬로 구현시 메모리 초과
인접행렬로 구현했을 때 O(VE) -> 1e51e5 메모리 256mb(=256(1e6)바이트) 초과

인접리스트로 간선 정보만 저장하여 해결
인접리스트로 BFS탐색을 구현하여 O(V+E) -> 1e5+1e5 메모리 256mb(=256(1e6)바이트) 미만

<시간 복잡도>

인접행렬로 구현시 시간 초과
인접행렬로 구현했을 때 O(VE) -> 1e51e5 시간초과

인접리스트로 간선 정보만 저장하여 해결
인접리스트로 BFS탐색을 구현하여 O(V+E) -> 1e5+1e5

<소요시간>

1시간 20분

<어려웠던 점>

간선의 정보를 저장하는 자료구조를 선정할 때 메모리와 시간복잡도를 고려해야하는 부분이 어려웠습니다.
주로 인접행렬방식을 이용했었는데, 인접리스트로 메모리와 시간복잡도를 줄일 수 있는 방법을 알게 되었습니다.
메모리와 시간복잡도를 생각하여 자료구조를 선정해야겠습니다.

해결 코드

import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

public class Main{
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();
    static ArrayList<ArrayList<Integer>> graph;
    static int[] parentNode;
    static int N;

    static void input(){
        N = scan.nextInt(); // 노드의 개수 입력
        graph = new ArrayList<ArrayList<Integer>>(); // 트리의 각 노드에 연결된 노드 번호 기록
        int i;
        for(i=0; i<N+1;i++) graph.add(new ArrayList<Integer>());
        parentNode = new int[N+1]; // i번째 노드의 부모노드 번호 저장

        int v1, v2;
        for(i=1; i<N; i++){
            v1 = scan.nextInt(); // 트리 상에서 연결된 두 정점
            v2 = scan.nextInt();
            graph.get(v1).add(v2); // 연결된 노드의 번호 저장
            graph.get(v2).add(v1);
        }
    }

    static void bfs(int n){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(n);
        while(!q.isEmpty()){
            int parent = q.poll();
            for(int child : graph.get(parent)){
                if (parentNode[child]==0){ // 자식노드의 부모노드를 기록하지 않은 경우
                    parentNode[child]=parent; // 현재 노드를 부모노드로 기록-
                    q.offer(child); // 자식노드를 q에 추가
                }
            }
        }
    }

    static void pro(){
        parentNode[1]=-1;
        bfs(1); // 루트 1에서 부터 자식 노드를 방문하여 부모노드 기록
        for(int i=2; i<N+1; i++) sb.append(parentNode[i]).append("\n");
        System.out.println(sb);
    }

    public static void main(String[] args){
        input();
        pro();
    }

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;

        FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next(){
            while(st==null||!st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }
    }
}

이중 우선순위 큐

오답 1 - 틀렸습니다

• 문제에서 각 값의 중복을 허용(같은 값이 있을 시 구분하여 삭제)하고 있다는 점을 발견하지 못하고 HashSet을 사용하여 이중 우선순위 큐를 구현하여 틀렸다.
• 다음으로 넘어가 중복을 구분할 수 있는 다른 풀이로 도전.
• HashSet 참고: https://coding-factory.tistory.com/554
• Double Ended Priority Queue 참고: https://www.geeksforgeeks.org/double-ended-priority-queue/

import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    // HashSet을 사용하여 이중 우선순위 큐를 구현한다.
    static class DualPriorityQueue{
        Set<Integer> s;
        DualPriorityQueue(){
            s = new HashSet<Integer>();
        }

        int size(){
            return s.size();
        }

        boolean isEmpty(){
            return (s.size()==0);
        }

        void insert(int x){
            s.add(x);
        }

        int getMax(){
            return Collections.max(s,null);
        }

        void deleteMax(){
            if (s.size() == 0) return;
            s.remove(Collections.max(s,null));
        }

        int getMin(){
            return Collections.min(s,null);
        }

        void deleteMin(){
            if (s.size() == 0) return;
            s.remove(Collections.min(s,null));
        }


    }
    public static void main(String[]args){
        /*[문제]
        이중 우선순위 큐
        우선순위 큐와의 공통점 삽입, 삭제할 수 있는 자료 구조인 점
        전형적인 큐와의 차이점 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점

        이중 우선순위 큐의 두 가지 연산
        데이터를 삽입
        (우선순위가 가장 낮은 것/우선순위가 가장 높은 것) 데이터를 삭제

        정수만 저장하는 이중 우선순위 큐
        저장된 각 정수의 값 자체를 우선순위로 간주
        큐에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값을 출력 */

        // 표준입력을 사용한다.
        // T개의 테스트 데이터를 입력받는다.
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for(int i=0; i<t; i++){
            // 이중 우선순위 큐를 선언한다.
            DualPriorityQueue dpq = new DualPriorityQueue();

            // Q에 적용할 연산의 개수를 나타내는 정수 k를 입력받는다.
            int k = scan.nextInt();
            for(int j=0;j<k;j++){
                // 연산을 나타내는 문자와 정수 n을 입력받는다.
                String str = scan.next();
                int n = scan.nextInt();
                // I n인 경우 n을 dpq에 삽입
                if (str.equals("I")) dpq.insert(n);
                // D 1인 경우 최댓값을 삭제
                else if (str.equals("D") && n==1) dpq.deleteMax();
                // D -1인 경우 최솟값을 삭제
                else if (str.equals("D") && n==-1) dpq.deleteMin();
            }

            if (dpq.isEmpty()) System.out.printf("EMPTY");
            else {
                System.out.printf(dpq.getMax()+" "+dpq.getMin());
            }
        }
    }
}

오답 2 - 시간 초과

• 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이기 때문에 최대, 최소를 알고 싶기 때문에 최소힙, 최대힙을 사용하여 구현해보았다.
• 하지만, getMin, getMax구현부에서 remove을 사용해 특정 값을 지우게 되는데 여기서 시간 복잡도가 O(n)으로 시간초과가 발생하게 된다. 왜냐하면 내부적으로 contains() 사용하게 되는데 탐색에서 O(n)이 되게된다.
• Priority Queue 참고: https://coding-factory.tistory.com/603
• Priority Queue remove time complexity 참고: https://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

import java.util.*;

public class Main {

    /*
        풀이 설계
        1. 삽입, 삭제 연산
        2. 우선순위에 다른 최대, 최소 값 탐색 필요
        3. 입력된 요청에 따라 삽입, 최대 삭제, 최소 삭제 -> 로직
        4. 정수를 저장하며 값 자체가 우선순위

        입력
        1. T개의 테스트
        2. K개의 연산 -> 100만 개의 값
            문자 명령어와 정수 값

        출력
        1. 최종적으로 자료구조에 저장된 최대, 최소 출력.
            비어있는 경우 "EMPTY"
    */

    static class DualPriorityQueue{

        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;

        DualPriorityQueue(){
            minHeap = new PriorityQueue<Integer>();
            maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        }

        int size(){
            return minHeap.size()+ maxHeap.size();
        }

        boolean isEmpty(){
            return (size() == 0);
        }

        void insert(int n){
            minHeap.offer(n);
            maxHeap.offer(n);
        }

        int getMax(){
            if (maxHeap.size() == 0) return 0;
            int max = maxHeap.poll();
            minHeap.remove(max);
            return max;
        }

        int getMin(){
            if (minHeap.size() == 0) return 0;
            int min = minHeap.poll();
            maxHeap.remove(min);
            return min;
        }
    }

    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);

        int T = scan.nextInt();
        for(int i=0; i<T; i++){

            DualPriorityQueue dpq = new DualPriorityQueue();

            int K = scan.nextInt();

            for(int j=0;j<K;j++){
                String str = scan.next();
                int n = scan.nextInt();

                if (str.equals("I")) dpq.insert(n);
                else if (str.equals("D") && n==1) dpq.getMax();
                else if (str.equals("D") && n==-1) dpq.getMin();
            }

            if (dpq.isEmpty()) System.out.println("EMPTY");
            else {
                System.out.println(dpq.getMax()+" "+dpq.getMin());
            }
        }
    }
}

해결 코드 - 맞았습니다!!

• TreeMap은 키와 값이 저장된 Map으로 Key와 개수를 저장하여 구현하였다.
• 또한, TreeMap은 저장 동시에 오름차순으로 정렬하여 최대값, 최소값을 바로 알 수 있다.
• TreeMap은 이진탐색트리의 문제점을 보완한 Red-Black Tree로 이루어져 있어 편향된 값 탐색도 문제가 없다.
• 풀이 참고: https://codeung.tistory.com/315
• TreeMap 참고:https://coding-factory.tistory.com/557
• TreeMap getOrDefault(key,defaultValue) method 참고: https://www.geeksforgeeks.org/hashmap-getordefaultkey-defaultvalue-method-in-java-with-examples/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    /*
        풀이 설계
        1. 삽입, 삭제 연산
        2. 우선순위에 다른 최대, 최소 값 탐색 필요
        3. 입력된 요청에 따라 삽입, 최대 삭제, 최소 삭제 -> 로직
        4. 정수를 저장하며 값 자체가 우선순위

        입력
        1. T개의 테스트
        2. K개의 연산 -> 100만 개의 값
            문자 명령어와 정수 값

        출력
        1. 최종적으로 자료구조에 저장된 최대, 최소 출력.
            비어있는 경우 "EMPTY"
    */

    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){

            TreeMap<Integer,Integer> treeMap = new TreeMap<>();
            int K = Integer.parseInt(br.readLine());

            for(int j=0;j<K;j++){
                st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if (str.equals("I")) treeMap.put(n, treeMap.getOrDefault(n,0)+1);
                else if (str.equals("D") && n==1 && !treeMap.isEmpty()){
                    int maxKey = treeMap.lastKey();
                    if(treeMap.get(maxKey) == 1) {
                        treeMap.remove(maxKey);
                    }else {
                        treeMap.put(maxKey, treeMap.get(maxKey) - 1);
                    }
                }
                else if (str.equals("D") && n==-1 && !treeMap.isEmpty()){
                    int minKey = treeMap.firstKey();
                    if(treeMap.get(minKey) == 1) {
                        treeMap.remove(minKey);
                    }else {
                        treeMap.put(minKey, treeMap.get(minKey) - 1);
                    }
                }
            }

            if (treeMap.isEmpty()) sb.append("EMPTY\n");
            else {
                sb.append(treeMap.lastKey()+" "+treeMap.firstKey()+"\n");
            }
        }
        System.out.println(sb);
    }
}

[Programmers] 조이스틱 -Python3

문제분석

1. 관찰
- "A"*len(name) 상태에서 주어진 name을 만들기위해 조이스틱을 상하좌우로 움직이는 최소 횟수를 구해야한다.
- 상하로 움직이는 경우는 각 자리의 문자와 "A"의 유니코드 정수의 차이를 사용하여 최소 횟수를 구할 수 있다.
- 하지만, 좌우로 이동하는 경우는 A의 유무, A의 연속된 길이, A의 위치에 따라 움직임을 고려해 주어야 하기 때문에 이를 고려하여 최소 움직임을 구해야한다.

- 다른 풀이들을 참고하였지만, 좌측으로 움직임, 우측으로 움직임을 수식으로 정리하여 최소 값을 구하는 방식이 직관적으로 이해가 되지 않았다.
- 따라서, 좌우 이동의 최소횟수를 구하기 위해서 최단거리를 구하는데 일반적으로 사용되는 BFS 알고리즘으로 접근하였다.

-  "A"*len(name)에서 주어진 name을 만들기 위해 A가 아닌 곳을 바꾸기위해 최소로 움직이며 모두 방문하여 주어진 name과 일치하도록 만들어주어야한다.
- 역으로, 주어진 name이 모두 A가 되게하는 최소 이동거리를 구해준다.

- name이 "A"*len(name)이 될 때까지 BFS를 해주며 좌우로 이동한 거리를 누적해준다.
- 이때, "A"*len(name)을 가장 빨리 만족하는 경우를 찾기위해 deque에 현재 name 의 상태를 deepcopy하여 기록해나가야한다.

2. 복잡도
- O(len(name) + len(name)) = 20 + 20 = 40
- 검토 필요

3. 자료구조
- 이름: str[]
- BFS: deque

해결코드

from collections import deque

def bfs(name):
    q = deque([(list(name), 0, 0)])

    while q:
        name_list, lr_cnt, idx = q.popleft()
        name_list[idx]='A'

        if name_list.count('A') == len(name):
            return lr_cnt

        for i in [-1,1]:
            name_copy = name_list[:]
            q.append((name_copy, lr_cnt+1, idx+i))

def solution(name):
    up_cnt = sum([min(abs(ord('A')-ord(n)), 26-abs(ord('A')-ord(n))) for n in name])
    lr_cnt = bfs(name)
    return up_cnt + lr_cnt

[Programmers] 징검다리 -Python3

문제분석

1. 관찰
- 맨 처음에는 n개를 지울 수 있는 모든 경우를 조합으로 구하여
모든 케이스에 대한 가장 작은 차이값 중 가장 큰 값을 출력하는 방식으로 접근했다.
- 하지만, 문제에서 주어진 것처럼 바위의 개수는 5만개이며 시작과 끝의 차이는 10억이다.

  - 5만개의 바위에서 n개를 제거한 조합을 찾는 시간복잡도는 5만이며
모든 케이스의 차이값을 탐색하기위해서는 5만*5만 이상이 소요된다. 
  - 따라서, 이 문제는 완전 탐색으로 접근하면 효율성 TC에 의해서 통과하지 못한다.

- 시간 복잡도를 개선하기위해서 이분탐색으로 문제를 접근해본다.
- 이분탐색으로 접근하게된다면 10억도 30번이면 탐색이 가능하고, 5만은 16번이면 탐색가능하다.

- 그래서, 어떻게 풀이를 해야하나?

- 우리가 찾는 값은 바위 n개를 제거했을 때 각 바위 사이의 거리를 측정하여 나온 최소거리 중에서 최대값이다.
- 따라서, 이분 탐색으로 찾는 값을 바위를 지우기 위한 최소 간격으로 설정하고 문제를 접근해 보아야 한다.

- 투 포인터를 통해 최소간격보다 작은 경우 해당 바위를 지운다. (시간복잡도 : len(rocks) => 5만)

- 지워진 바위의 개수가 n보다 크면 상한값을 축소(최소 간격을 감소)시키고,
- 지워진 바위의 개수가 n이하이면 하한값을 축소(최소 간격을 증가)시킨다. 

- 그렇게 n개를 지우는 경우에 대하여 low와 high가 같아질 때 까지 이분탐색을 반복해주면 mid 값은 n개를 제거하는 최소간격 중 최대값을 만족한다.

2. 복잡도
- O(log2(dis)*rocks) = 16*5만 => 약 90만
- 이분탐색을 통해 가능

3. 자료구조
- 바위 거리 : int[]
- n개를 제거하는 간격: int

해결코드

def solution(distance, rocks, n):

    answer = 0
    rock_list = sorted(rocks) + [distance] # 50,000

    low = 0
    high = distance
    idx=0

    while low <= high: # log2(50,000) = 약 16
        mid = (low+high)//2
        current = 0
        remove = 0 

        idx += 1
        for rock in rock_list:
            diff = rock - current 
            if diff >= mid:
                current = rock
            else:
                remove += 1

        if remove > n:
            high = mid -1
        else:
            low = mid + 1 
            answer = mid 

    return answer

[Programmers] 전력망을 둘로 나누기 -Python3

문제분석

1. 관찰
- 송전탑이 전선을 통해 하나의 트리(Tree) 형태로 연결되어 있다.
- 따라서 송전탑은 '노드', 전선은 '간선'으로 이해할 수 있다.

- 문제에서 요구하기를 전력망 네트워크를 2개로 분할하려고 한다.
- 주어진 간선의 개수가 99개 이하임으로 완전 탐색을 구현해도 된다.
  - wires 중 하나를 제거하면 네트워크가 2개로 분할되는 것을 이용해 완전 탐색을 한다.

- 2개로 분할된 모든 경우에 대하여 두 네트워크의 노드 개수를 비교하고 최소값을 출력한다.
  - 분할된 한 네트워크에 대하여 BFS하여 노드의 개수를 구한다.
  - 전체 노드의 개수 n을 사용하여 두 네트워크의 노드의 개수를 비교한다.

2. 복잡도
- O(V*(V+E)) =  99 * (99 + 100)  => 그냥 가능이다.
- 합리적으로 완전탐색을 시도할 수 있다.

3. 자료구조
- 트리: int[][]
- 방문 처리: int[]

해결코드

from collections import deque

def bfs(tree, start, visited):
    q = deque([start])
    visited.append(start)
    while q:
        now = q.popleft()
        for nxt in tree[now]:
            if nxt not in visited:
                q.append(nxt)
                visited.append(nxt)
    return len(visited)

def solution(n, wires):

    answer = n

    for i in range(len(wires)):
        tree = [[] for _ in range(n)]
        for idx, wire in enumerate(wires):
            if idx==i:
                continue
            tree[wire[0]-1].append(wire[1]-1)
            tree[wire[1]-1].append(wire[0]-1)

        one = bfs(tree, 0, [])

        result = abs((n - one) - one)

        if answer > result:
            answer = result

    return answer