알고리즘 재활 13일차 - 15663, 1149, 1753번

 

해장.. 알고리즘

 

 

N과 M (9)

 

 

 

중복되는 수열을 제외하고 출력해주는게 포인트이다

따라서 정렬한 arr 배열에서 수로 수열을 만들때 이전 수와 같은지 체크해주었다.

if (!visit[i] && arr[i] != prev)

 

import java.io.*;
import java.util.*;
 
public class Main { // N과 M (9)
    public static int N, M;
    public static StringBuilder sb;
    public static boolean[] visit;
    public static int[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        visit = new boolean[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        dfs(0, new int[M]);
 
        System.out.println(sb);
    }
 
    public static void dfs(int depth, int[] nums ) {
        if (depth == M) {
            for (int s : nums) {
                sb.append(s).append(" ");
            }
            sb.append("\n");
            return;
        }
 
        int prev = -1;
        for (int i = 0; i < N; i++) {
            if (!visit[i] && arr[i] != prev) {
                visit[i] = true;
                nums[depth] = arr[i];
                prev = arr[i];  // 현재 값을 이전 값으로 업데이트
                dfs(depth + 1, nums);
                visit[i] = false;
            }
        }
    }
}
 

---

RGB거리

 

 

 

간단한 DP 문제였다,

1자로 집이 나열되어 있기 때문에 이전 집만 고려해주면 됐다.

따라서 i 번째 집의 색은 이전과만 다르게 DP로직을 구성하고 DP 배열에 저장된 마지막 인덱스의

최소값을 찾아주면 된다.

 

간단한 점화식

dp[i][0] = (Math.min(dp[i-1][1], dp[i-1][2])) + arr[i][0];
dp[i][1] = (Math.min(dp[i-1][0], dp[i-1][2])) + arr[i][1];
dp[i][2] = (Math.min(dp[i-1][1], dp[i-1][0])) + arr[i][2];

 

import java.io.*;
import java.util.*;
 
public class Main { // RGB거리
    public static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        int [][] arr = new int[N][3];
        int [][] dp = new int[N][3];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < 3 ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for(int i = 0; i < 3; i++) {
            dp[0][i] = arr[0][i];
        }
        for(int i = 1; i < N; i++) {
            dp[i][0] = (Math.min(dp[i-1][1], dp[i-1][2])) + arr[i][0];
            dp[i][1] = (Math.min(dp[i-1][0], dp[i-1][2])) + arr[i][1];
            dp[i][2] = (Math.min(dp[i-1][1], dp[i-1][0])) + arr[i][2];
        }
 
        int answer = Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2]));
 
        System.out.println(answer);
    }
}
 

 

---

최단경로

 

 

 

방향그래프 였던 거시와요..

우선순위 큐 활용해서 가중치가 낮은것부터 해당 위치에 가는 비용을 갱신해줍시다.

다익스트라로 해결~ 

 

 

import java.io.*;
import java.util.*;
 
public class Main { // 최단경로
    public static int V, E, K;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        K = Integer.parseInt(br.readLine());
 
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }
 
        int[] cost = new int[V + 1];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[K] = 0;
 
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(u).add(new Node(v, w));
        }
 
        dijkstra(K, graph, cost);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (cost[i] == Integer.MAX_VALUE) {
                sb.append("INF\n");
            } else {
                sb.append(cost[i]).append("\n");
            }
        }
 
        System.out.println(sb.toString());
    }
 
    public static void dijkstra(int start, List<List<Node>> graph, int[] cost) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.cost));
        pq.add(new Node(start, 0));
 
        while (!pq.isEmpty()) {
            Node cr = pq.poll();
            int crNode = cr.idx;
            int crCost = cr.cost;
 
            if (crCost > cost[crNode]) continue;
 
            for (Node n : graph.get(crNode)) {
                int newCost = crCost + n.cost;
                if (newCost < cost[n.idx]) {
                    cost[n.idx] = newCost;
                    pq.add(new Node(n.idx, newCost));
                }
            }
        }
    }
 
    static class Node {
        int idx;
        int cost;
 
        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
}