CODEKATA : 113 ~ 114

113번 무인도 여행

/*
문제 분석
1. 정보
    - n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다.
    - 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 한다.
    - 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.
2. 목표
    -송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어졌을때, 두 전력망이 가지고 있는 송전탑 개수의 차이를 return
3. 제약 조건
    - 2 <= n <= 100
    - wires는 길이가 n-1인 2차원 배열
        - wires의 각 원소는 [v1,v2]로 이루어져 있고, 이는 v1번 송전탑과 v2번 송전탑이 전선으로 연결 되어 있다는 것을 의미


풀이
1. 아이디어
    - 인접한 번호를 저장하는 리스트를 생성
    - 하나의 간선을 제거하고, BFS 사용하여 한쪽 서브트리의 노드 개수를 구함
    - 전체 노드 개수에서 한쪽 서브트리의 노드 개수를 빼면 다른 서브 트리의 크기 얻기 가능
    - 두 서브트리의 차이를 계산하고 최소값 갱신(절댓값)

*/

import java.util.*;

class Solution {
        List<List<Integer>> list = new ArrayList<>();
        boolean[] visited;
        int answer = 1000;
    
        public int solution(int n, int[][] wires) {
            for (int i = 0; i <= n; i++) {
                list.add(new ArrayList<>());
            }

            for (int[] wire : wires) {
                list.get(wire[0]).add(wire[1]);
                list.get(wire[1]).add(wire[0]);
            }

            for (int[] wire : wires) {
                int v1 = wire[0];
                int v2 = wire[1];

                list.get(v1).remove(Integer.valueOf(v2));
                list.get(v2).remove(Integer.valueOf(v1));

                visited = new boolean[n + 1];

                int subTree = BFS(v1);
                int remain = n - subTree;
                answer = Math.min(answer, Math.abs(subTree - remain));

                list.get(v1).add(v2);
                list.get(v2).add(v1);
            }
            return answer;
        }

        private int BFS(int v1) {
            int cnt = 1;
            Queue<Integer> q = new LinkedList<>();
            q.add(v1);
            visited[v1] = true;

            while (!q.isEmpty()) {
                int cur = q.poll();

                for (Integer next : list.get(cur)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.add(next);
                        cnt++;
                    }
                }
            }

            return cnt;
        }
    }

114번 행렬 테두리 회전하기

/*
문제 분석
1. 정보
    - N개의 마을로 이루어진 나라가 있음.
    - 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있다.
    - 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 해당 도로를 지나야 함.
    - 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 함.
    - 각 마을로 부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 함.
2. 목표
    - 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개 변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return
3. 제약 조건
    - 1 <= N <= 50
    - 1 <= road의 길이 <= 2000
    - 1 <= K <= 500000
    
풀이
1. 아이디어
    - Priority Queue 및 DFS를 활용하여 시작 지점에서 i 지점까지 가는데 최소 시간을 구함.
    - 만약 최소 시간이 K보다 크다면, 해당 마을은 배달 불가함.
    - 따라서 결과 값에서 빼줌
*/

import java.util.*;

class Solution {

        class Node implements Comparable<Node>{
            int e;
            int d;

            public Node(int e, int d) {
                this.e = e;
                this.d = d;
            }
            
            @Override
            public int compareTo(Node o){
                return this.d - o.d;
            }
        }

        public int solution(int N, int[][] road, int K) {
            List<Node>[] list = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            for (int[] info : road) {
                int s = info[0];
                int e = info[1];
                int d = info[2];
                list[s].add(new Node(e, d));
                list[e].add(new Node(s, d));
            }

            boolean[] visited = new boolean[N + 1];
            int[] dist = new int[N + 1];
            Arrays.fill(dist, 500001);
            int answer = 0;
            PriorityQueue<Node> pq = new PriorityQueue<>();

            pq.add(new Node(1, 0));
            dist[1] = 0;
            while (!pq.isEmpty()) {
                Node cur = pq.poll();

                if (visited[cur.e]) {
                    continue;
                }
                visited[cur.e] = true;

                for (Node next : list[cur.e]) {
                    if (!visited[next.e] && dist[next.e] > dist[cur.e] + next.d) {
                        dist[next.e] = dist[cur.e] + next.d;
                        pq.add(new Node(next.e, dist[next.e]));
                    }
                }
            }

            for (int i = 1; i <= N; i++) {
                if(dist[i] <= K){
                    answer++;
                }
            }
            return answer;
        }
    }