알고리즘 재활 9일차 - 백준 2096, 13549, 10159, 1719번

후딱 공부하고 놀러갑시다.. ㅣㅎ히ㅣ

 

내려가기 

 

간단하다. 가로 3칸인 상태에서 1칸씩 밑으로 내려오고 인접한곳으로만 내려올 수 있다.

이 경로들에 숫자가 있고 이 값들의 합을 구해야한다.

2가지가 요구되는데 최대값과 최솟값을 구하는 문제다.

 

DP가 떠올랐고, 점화식 넣어주자

Dp[i][j] 가 현재 내려오는 장소에 따라 다르게 조건을 넣어주자.

 

첫번째 칸이라면 첫번째와 두번째칸을 비교해주고,

두번째 칸이라면 세칸 모두를 비교해준다.

세번째 칸이라면 두번째와 세번째칸을 비교해주었다.

maxDp[i][0] = Math.max(maxDp[i - 1][0], maxDp[i - 1][1]) + map[i][0];
maxDp[i][1] = Math.max(Math.max(maxDp[i - 1][1], maxDp[i - 1][2]), maxDp[i - 1][0]) + map[i][1];
maxDp[i][2] = Math.max(maxDp[i - 1][2], maxDp[i - 1][1]) + map[i][2];

 

요로코롬

 

 

import java.io.*;
import java.util.*;
 
public class Main { // G5 최소비용 구하기
 
    public static int N;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
 
        StringTokenizer st;
        int[][] map = new int[N][3];
        int[][] minDp = new int[N][3];
        int[][] maxDp = new int[N][3];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        minDp[0][0] = map[0][0];
        minDp[0][1] = map[0][1];
        minDp[0][2] = map[0][2];
        maxDp[0][0] = map[0][0];
        maxDp[0][1] = map[0][1];
        maxDp[0][2] = map[0][2];
 
        for (int i = 1; i < N; i++) {
            maxDp[i][0] = Math.max(maxDp[i - 1][0], maxDp[i - 1][1]) + map[i][0];
            maxDp[i][1] = Math.max(Math.max(maxDp[i - 1][1], maxDp[i - 1][2]), maxDp[i - 1][0]) + map[i][1];
            maxDp[i][2] = Math.max(maxDp[i - 1][2], maxDp[i - 1][1]) + map[i][2];
        }
        sb.append(Math.max(maxDp[N-1][2], Math.max(maxDp[N-1][0], maxDp[N-1][1]))).append(" ");
 
        for (int i = 1; i < N; i++) {
            minDp[i][0] = Math.min(minDp[i - 1][0], minDp[i - 1][1]) + map[i][0];
            minDp[i][1] = Math.min(Math.min(minDp[i - 1][1], minDp[i - 1][2]), minDp[i - 1][0]) + map[i][1];
            minDp[i][2] = Math.min(minDp[i - 1][2], minDp[i - 1][1]) + map[i][2];
        }
        sb.append(Math.min(minDp[N-1][2], Math.min(minDp[N-1][0], minDp[N-1][1])));
        System.out.println(sb);
    }
}
 

---

숨바꼭질 3

 

처음에는 DP를 떠올렸다가 순간이동에는 비용이 0초고 도착하면 끝이니까 큐 활용 BFS로 풀기로 했다.

일단 조건은 현재 값이 목표의 반절보다 적다면 순간이동에 넣어주고

목표보다 작다면 +1도 넣어주고, 크다면 -1도 넣어줬다.

 

우리는 큐를 활용해서 최단시간을 계산하므로 값은 += 이 아닌 값을 갱신해줬다.

결론적으로 목표 숫자와 같아지면 종료

 

import java.io.*;
import java.util.*;
 
public class Main { // G5 숨바꼭질3
 
    public static int N, M;
 
    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());
        M = Integer.parseInt(st.nextToken());
 
        if (N == M) {
            System.out.println(0);
            return;
        }
 
        int[] dist = new int[Math.max(N, M) * 2 + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[N] = 0;
 
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(N);
 
        while (!queue.isEmpty()) {
            int now = queue.poll();
 
            if (now == M) {
                break;
            }
 
            if (now * 2 < dist.length && dist[now * 2] > dist[now]) {
                dist[now * 2] = dist[now];
                queue.add(now * 2);
            }
 
            if (now - 1 >= 0 && dist[now - 1] > dist[now] + 1) {
                dist[now - 1] = dist[now] + 1;
                queue.add(now - 1);
            }
 
            if (now + 1 < dist.length && dist[now + 1] > dist[now] + 1) {
                dist[now + 1] = dist[now] + 1;
                queue.add(now + 1);
            }
        }
 
        System.out.println(dist[M]);
    }
}
 

 

 

---

저울

 

처음에 잘못생각해서 고생을 한.. 문제다.

저울로 서로서로 무게를 비교하면서 서로 누가 더 무거운지 알 수 없는 관계가 몇개인지 출력하는 문제다.

 

간단하게 서로의 무게를 비교할 수 있다는것은 연결그래프처럼 연관관계가 있으면 파악할 수 있으니까

아 이거 DFS로 서로 연결되었나 확인하면 되겠구나 생각했었다. < 아이고~~ 아이고

 

만약 이렇게 주어진다면?

내가 생각한 흐름으로 진행했더라면 1과 2는 4에 대한 정보가 없었음에도 판단할 수 있는 로직을 작성했을것이다.

이거를 거의 1시간 값이 이상해서 낑낑꽁 거리다가 같이 스터디하는 형이랑 얘기하다 눈치챘다..

양방향 그래프로 작성할것이 아니라, 그래프를 나눠서  누가 더 크고 작은지를 관리해주었다

 

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            larger.get(a).add(b);
            smaller.get(b).add(a);
        }

 

요로코롬

이후에 각자 나누어진 데이터로 DFS를 순회하며 visited으로 해당 넘버와 무게를 비교할 수 있는지 체크한다.

이제 무게비교를 큰지 작은지로 나누어서 boolean에 담았다.

그럼 우리는 서로가 크고 작은 데이터가 동시에 존재할때 서로의 무게를 판단할 수 있구나! 를 내려주면 된다.

 

import java.io.*;
import java.util.*;
 
public class Main { // G4 저울
 
    public static int N, M;
    public static ArrayList<ArrayList<Integer>> larger;
    public static ArrayList<ArrayList<Integer>> smaller;
    public static int[] answer;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
 
        larger = new ArrayList<>();
        smaller = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            larger.add(new ArrayList<>());
            smaller.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            larger.get(a).add(b);
            smaller.get(b).add(a);
        }
 
        answer = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            boolean[] visitedLarger = new boolean[N + 1];
            boolean[] visitedSmaller = new boolean[N + 1];
 
            dfsFindLarger(i, visitedLarger);
            dfsFindSmaller(i, visitedSmaller);
 
            int count = 0;
            for (int j = 1; j <= N; j++) {
                if (i != j && !visitedLarger[j] && !visitedSmaller[j]) {
                    count++;
                }
            }
            answer[i] = count;
        }
 
        for (int i = 1; i <= N; i++) {
            sb.append(answer[i]).append("\n");
        }
        System.out.print(sb);
    }
 
    public static void dfsFindLarger(int now, boolean[] visited) {
        visited[now] = true;
        for (int next : larger.get(now)) {
            if (!visited[next]) {
                dfsFindLarger(next, visited);
            }
        }
    }
 
    public static void dfsFindSmaller(int now, boolean[] visited) {
        visited[now] = true;
        for (int next : smaller.get(now)) {
            if (!visited[next]) {
                dfsFindSmaller(next, visited);
            }
        }
    }
}
 

---

택배

 

이것도.. 진짜 온종일 걸린 문제다.

다익스트라 문제 + 경로 추적까지 해야하는 문제라 까다롭게 다가왔다.

먼저 다익스트라로 경로를 갱신할때는 탐색하지 않은 장소는 무한대로두고 경로를 비교해가면서 갱신해준다.

이 문제는 해당번호로 가는 가장 짧은 경로중 첫번째로 방문하는곳이 어딘가? 를 물었다.

 

예를들어 1번에서 6번으로 이동한다고 가정해보자

1번에서 6번으로 가는 가장 빠른 방법은 1 > 2 >  5 > 6 으로 이동하는 방법이 2 + 3 + 2 = 7으로 가장 빠르다.

그러면 [1][6]에는 첫번째 경로인 2를 출력해야한다.

 

다익스트라를 활용해서 갱신하고, 갱신될때 그 경로를 저장해주었다.

2에서 6으로 가는경로에서 2 > 5 > 6이 더 빠르다고 갱신된다면
answer[2][6] = 5 가 되는것이다. 여기서 5는 현재 탐색하는 IDX가 된다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main { // G3 택배
 
        static ArrayList<ArrayList<Node>> CJ;
        public static int N, M;
        public static int[][] answer;
        public static int[] distances;
        public static int[] prev;
 
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
 
            CJ = new ArrayList<>();
            answer = new int[N + 1][N + 1];
            distances = new int[N + 1];
            prev = new int[N + 1];
 
            for (int i = 0; i <= N; i++) {
                CJ.add(new ArrayList<>());
            }
 
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int distance = Integer.parseInt(st.nextToken());
                CJ.get(start).add(new Node(end, distance));
                CJ.get(end).add(new Node(start, distance));
            }
 
            // 최단 경로 찾기
            for (int i = 1; i <= N; i++) {
                dijkstra(i);
            }
 
            // 경로 출력
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) {
                        sb.append("- ");
                    } else {
                        sb.append(answer[i][j]).append(" ");
                    }
                }
                sb.append("\n");
            }
 
            System.out.print(sb);
        }
 
        static void dijkstra(int start) {
            boolean[] visited = new boolean[N + 1];
            Arrays.fill(distances, Integer.MAX_VALUE);
            Arrays.fill(prev, -1);
 
            PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
            pq.add(new Node(start, 0));
            distances[start] = 0;
 
            while (!pq.isEmpty()) {
                Node curNode = pq.poll();
                int curIdx = curNode.idx;
                if (visited[curIdx]) {
                    continue;
                }
                visited[curIdx] = true;
 
                for (Node nextNode : CJ.get(curIdx)) {
                    int nextIdx = nextNode.idx;
                    int newCost = distances[curIdx] + nextNode.cost;
                    if (newCost < distances[nextIdx]) {
                        distances[nextIdx] = newCost;
                        answer[nextIdx][start] = curIdx;
                        pq.add(new Node(nextIdx, distances[nextIdx]));
                    }
                }
            }
        }
 
        public static class Node {
            int idx, cost;
 
            Node(int idx, int cost) {
                this.idx = idx;
                this.cost = cost;
            }
        }
    }