[프로그래머스] Lv3 문제풀이6(feat. JAVA)

가장 먼 노드

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        ArrayList<Integer>[] list = new ArrayList[n+1];

        for(int[] e : edge) {
            int x = e[0];
            int y = e[1];

            if(list[x] == null) list[x] = new ArrayList<>();
            list[x].add(y);
            if(list[y] == null) list[y] = new ArrayList<>();
            list[y].add(x);
        }

        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visit = new boolean[n+1];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        dist[1] = 0;

        while(!queue.isEmpty()) {
            int q = queue.poll();
            if(visit[q]) continue;

            for(int i = 0; i < list[q].size(); i++){
                if(list[q].size() == 0) continue;
                int num = list[q].get(i);
                dist[num] = Math.min(dist[num], dist[q] + 1);
                queue.add(num);
            }
            list[q].clear();
            visit[q] = true;
        }

        int[] dist_cnt = new int[n+1];
        int max = Arrays.stream(dist, 1, n+1).max().getAsInt();
        answer = Math.toIntExact(Arrays.stream(dist, 1, n+1).filter(i -> i==max).count());
        return answer;
    }
}

 

 

 

섬 연결하기

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int[] parent;
    public class Bridge {
        int x;
        int y;
        int c;

        Bridge(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
    public boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) return false;

        if(a > b)
            parent[b] = a;
        else
            parent[a] = b;

        return true;
    }

    public int find(int x) {
        if(parent[x] == x) return x;
        return find(parent[x]);
    }
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        IntStream.range(0, n).forEach(i -> parent[i] = i);

        ArrayList<Bridge> blist = new ArrayList<>();
        IntStream.range(0, costs.length)
                .forEach(i -> blist.add(new Bridge(costs[i][0], costs[i][1], costs[i][2])));
        blist.sort(((o1, o2) -> o1.c - o2.c));

        for(Bridge b : blist) {
            if(union(b.x, b.y)) {
                answer += b.c;
            }
        }

        return answer;
    }
}

 

 

 

여행 경로

import java.util.*;
import java.util.stream.IntStream;
class Solution {
    int cnt = 0;
    List<Integer> list1 = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        Map<String, Integer> indexing = new HashMap<>();
        List<String> tlist = new ArrayList<>();

        for(String[] ticket : tickets) {
            for(String t : ticket) {
                if(!tlist.contains(t))
                    tlist.add(t);
            }
        }
        cnt = tickets.length;
        tlist.sort(Comparator.naturalOrder());

        IntStream.range(0, tlist.size()).forEach(i -> {
            indexing.put(tlist.get(i), i);
        });

        int[][] arr = new int[tlist.size()][tlist.size()];
        IntStream.range(0, tickets.length).forEach(i -> {
            arr[indexing.get(tickets[i][0])][indexing.get(tickets[i][1])]++;
        });

        int start = indexing.get("ICN");
        list1.add(start);
        dfs(arr, start, 0);

        List<String> rst = new ArrayList<>();
        IntStream.range(0, list2.size())
                .forEach(i -> {
                    indexing.keySet().stream().forEach(key -> {
                        if(indexing.get(key) == list2.get(i)){
                            rst.add(key);
                        }
                    });
                });

        return rst.toArray(new String[0]);
    }
    List<Integer> list2 = new ArrayList<>();
    public void dfs(int[][] arr, int start, int count) {
        if(count == cnt && list2.size() == 0) {
            list2.addAll(list1);
            return;
        }

        for(int i = 0; i < arr[start].length; i++){
            if(arr[start][i] >= 1) {
                arr[start][i]--;
                List<Integer> l = new ArrayList<>(list1);
                list1.add(i);
                dfs(arr, i, count+1);
                arr[start][i]++;
                list1 = new ArrayList<>(l);
            }
        }
    }
}