📙[Algo] 24.05.13 알고리즘

📙 Algorithm Solving/Java

📙[Algo] 24.05.13 알고리즘

혜덕hyeduck 2024. 5. 13. 17:05

알고리즘 문제) BOJ 14676. 영우는 사기꾼?

링크 : https://www.acmicpc.net/problem/14676

문제 요약

우주 전쟁
- 건물을 짓는 순서가 정해져있음
  - ex) 1번 건물을 지어야 2번, 3번 건설 가능 = 1번 건물이, 2,3,번에 영향을 미친다
- 한 건물은 최대 3개 건물에게만 영향을 미칠 수 있으며, 중복 건설이 가능하다.
- 치트키 ⇒ 원하는 건물을 마음대로 지을 수 있음
주어진 정보를 보고 영우가 치트키를 사용했는지 안헀는지 파악하기

시간 제한

1초

입력

첫째 줄 : 건물 종류 개수 N, 건물 사이 관계 수 M, 영우의 게임 정보 개수 K
- 1 ≤ N,M,K ≤ 10만
다음 M개의 줄에 걸쳐 건물 관계인 X, Y가 차례대로 중복 없이 주어짐
- X를 건설해야 Y건설 가능
  - 1 ≤ X, Y ≤ N
다음 줄부터 K줄에 걸쳐 영우의 게임 정보가 주어짐 ( 1 ≤ a ≤ N)
- 1 a
  - 영우가 a번 건물을 1개 건설
- 2 a
  - 영우의 a번 건물이 1개 파괴

출력

영우가 정상적으로 건물을 건설하고나, 건설한 만큼 건물만 파괴 되었다면 King-God-Emperor 출력
건설할 수 없는 건물을 건설하거나, 건설한적 없는 건물이 파괴되었다면 Lier! 출력

접근법

시간초과 해결하기 위해 위상정렬 알고리즘이 무엇인지 공부했다.
하지만 이 문제는 새로운 타입(?)으로 위상정렬 알고리즘을 푼 느낌이다.
결국 다른 사람 해설법을 참고해서 시간초과를 해결함
- 우선, 게임 정보마다 건물을 지을 때 부모 건물이 지어졌는지 체크해가면 최악의 경우 10만*10만으로 당연히 시간초과가 뜰 수밖에 없음
- 따라서 pCnt라는 배열을 추가로 만들어서 조건을 걸어서 체크해나갔다.
  - pCnt배열 → 현재 부모 건물이 지어졌는지 판단하는 배열
    - 우선 건물 관계정보를 입력 받을 때, 현재 건물의 부모 개수만큼 +1해준다.
      - 부모 = 짓기 전에 미리 지어져 있어야 하는 건물
    - 그리고 게임 정보가 주어질 때, 만약 건물을 짓게 된다면
      - pCnt가 0인 경우에만 짓게 했다.
        
        즉, 미리 지어야 할 건물이 모두 지어졌다는 의미
        
        또한 건물을 짓게 되면, 내 자식들의 pCnt값을 1씩 감소 시킨다. ⇒ 즉, 부모가 건설 되어있으니, 이미 지어졌다는 의미로 1 감소
        
        그러나, 모든 상황에서 해당 로직을 돌리는 게 아니다. 건물을 중복해서 건설할 수 있기 때문에, 지어진 건물 개수(isBuild)가 1개인 경우에만 돌리게 했다.
    - 건물을 파괴하게 된다면
      - 지어진 건물 개수(isBuild)가 0이하면 파괴가 불가능
      - 그게 아니라면,
        
        idBuild개수를 1감소 시키고
        
        해당 건물이 파괴 되었으므로, 자식들의 pCnt를 1씩 증가시킨다. ⇒ 지어져야할 부모 건물이 지어지지 않았다는 의미
        
        이거 역시 isBuild가 0일때만 돌릴것
        
        중복 건설이 가능하기 때문에 isBuild가 양수일 경우에는 자식들의 pCnt를 감소시키면 X

코드

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


public class Main {
    static int N, M, K;
    static ArrayList<Integer>[] childs;
    static int[] isBuild;
    static int[] pCnt;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 건물 종류 개수
        M = Integer.parseInt(st.nextToken()); // 건물 사이 관계 개수
        K = Integer.parseInt(st.nextToken()); // 영우 게임 정보 개수

        childs = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            childs[i] = new ArrayList<>();
        }
        isBuild = new int[N + 1];
        pCnt = new int[N + 1];

        int p, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            childs[p].add(c);
            pCnt[c]++;
        }

        int cmd, no;
        boolean isAble = true;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            cmd = Integer.parseInt(st.nextToken());
            no = Integer.parseInt(st.nextToken());

            if (cmd == 1) {
                // 건물 짓기
                // 조건 : 내 부모가 이미 지어져 있어야 함
                if (pCnt[no] == 0) {
                    // 현재건물에 영향을 미치는 건물이 없다면
                    isBuild[no]++;

                    // 이미 지어져있으니, 자식들의 pCnt는 낮추기
                    if (isBuild[no] == 1) {
                        // isBuild[no] == 1조건 준 이유 --> 건물은 중복해서 건설이 가능
                        // 즉 같은 건물을 여러번 짓게 되면, pCnt값이 음수가 나올 수 있다.
                        for (Integer child : childs[no]) {
                            pCnt[child]--;
                        }
                    }
                } else {
                    isAble = false;
                }
            } else if (cmd == 2) {
                // 건물 파괴
                // 조건 : 건설된 건물만 파괴해야함
                if (isBuild[no] > 0){
                    isBuild[no]--;

                    if (isBuild[no] == 0) {
                        // 건물이 없다면, pCnt 늘리기 -> 이걸로 지을 수 있는지 판단하니까
                        // isBuild[no] == 0 조건을 준 이유 --> 건물은 중복해서 건설 가능
                        // 즉, 아예 건물이 존재하지 않은 경우에만 pCnt를 늘려준다.
                        for (Integer child : childs[no]) {
                            pCnt[child]++;
                        }
                    }
                } else{
                    isAble = false;
                }
            }
        }

        if (!isAble) System.out.println("Lier!");
        else System.out.println("King-God-Emperor");

        br.close();
    }
}

알고리즘 문제) BOJ 1761. 정점들의 거리

링크 : https://www.acmicpc.net/problem/1761

문제 요약

N개의 정점으로 이루어진 트리가 주어지고, M개의 두 노드 쌍을 입력 받을 때 두 노드 사이 거리 출력

시간 제한

2초

입력

노드 개수 N
- 2 ≤ N ≤ 4만
다음 N-1개 줄에 트리 상 연결된 두 점과 거리가 주어짐
- 거리는 1만보다 작은 자연수
거리를 알고 싶은 노드 쌍 개수 M
- 1 ≤ M ≤ 1만
M개 줄에 노드 쌍이 주어짐

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력

접근법

공통 조상 알고리즘을 학습했다.
- 루트 노드를 1로 가정한 트리를 구성할 것
  - 부모노드와 현재 노드의 깊이를 저장할 배열 parent, depth를 만들어서 진행한다.
  - 그러나, 이 문제에서는 두 노드간 거리를 구하는 문제라서 추가로 루트로부터의 거리를 저장할 distFromRoot배열도 만들었다.
  - dfs를 돌리면서 자식 노드의 부모 노드, 깊이, 루트로부터 거리를 각각 갱신해주었다.
- 그 다음 lca를 찾는 함수를 만든다.
  - 매개변수로 lca를 찾을 두 노드 v1, v2를 넘겨준다.
  - 먼저, 깊이가 더 깊은 노드를 v2로 맞춰준다.
  - 그다음, 두 노드 깊이가 같아질 때까지 v2를 계속해서 올려준다.
  - 두 노드 깊이가 같아진 상태에서 동시에, 두 노드가 같아질 때까지 두 노드의 부모 노드로 올려준다(위로 올리기).
  - 최종적으로 v1또는 v2를 반환 → 해당 노드가 LCA
- 이제, 입력으로 주어진 v1, v2의 거리를 찾아보자
  - 먼저 lca(v1,v2)를 통해 공통 조상(lca)를 찾는다.
  - 두 노드의 거리는 각 노드가 lca까지의 거리의 합이 된다.
    - 따라서 (distFromRoot[v1] - distFromRoot[lca]) + (distFromRoot[v2] - distFromRoot[lca]) 가 답이 된다.
      - distFromRoot배열에는 루트노드로부터 거리가 저장 되어 있기 때문에, 각각 노드의 distFromRoot값에서 루트에서 lca까지 값인 distFromRoot[lca]를 뺀 거리의 합이 답이됨.

코드

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


public class Main {
    static int N, M;
    static ArrayList<Node>[] lst;
    static int[] parent;
    static int[] depth;
    static int[] distFromRoot;

    static class Node {
        int no;
        int dist;

        Node(int no, int dist) {
            this.no = no;
            this.dist = dist;
        }
    }

    // 트리 구성하기
    static void dfs(int cur, int prv, int dist) {
        int nxt, nd;
        for (Node node : lst[cur]) {
            nxt = node.no;
            nd = node.dist;

            if (prv == nxt) continue;

            // 깊이 갱신
            depth[nxt] = depth[cur] + 1;
            // 부모 노드 갱신
            parent[nxt] = cur;
            // 루트로부터 누적 거리 갱신
            distFromRoot[nxt] = dist + nd;
            dfs(nxt, cur, dist + nd);
        }
    }

    // 공통 조상 LCA 찾기
    static int lca(int v1, int v2) {
        // 깊이가 더 큰 쪽을 n2로 맞춰주기
        if (depth[v1] > depth[v2]) {
            int tmp = v1;
            v1 = v2;
            v2 = tmp;
        }

        // 두 노드가 같은 깊이가 될 떄까지
        while (depth[v1] != depth[v2]) {
            v2 = parent[v2];
        }

        // LCA 찾기
        while (v1 != v2) {
            v1 = parent[v1];
            v2 = parent[v2];
        }

        return v1;
    }

    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());

        lst = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            lst[i] = new ArrayList<>();
        }

        int v1, v2, d;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());

            lst[v1].add(new Node(v2, d));
            lst[v2].add(new Node(v1, d));
        }

        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }
        depth = new int[N + 1];
        distFromRoot = new int[N + 1];

        // 루트가 1인 트리 구성
        dfs(1, 0, 0);

        M = Integer.parseInt(br.readLine());
        int lca, dist;
        for (int i = 0; i < M; i++) { // 1만
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());

            lca = lca(v1, v2);

            dist = (distFromRoot[v1] - distFromRoot[lca])
                    + (distFromRoot[v2] - distFromRoot[lca]);

            sb.append(dist).append("\n");
        }

        System.out.println(sb);

        br.close();
    }
}

알고리즘 문제) BOJ 17485. 진우의 달 여행 (Large)

링크 : https://www.acmicpc.net/problem/17485

문제 요약

지구와 우주사이는 N X M 행렬로 나타낼 수 있으며
각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양
우주선은 다음과 같은 특징이 존재
- 지구 → 달로 가기 위해서 우주선이 움직일 수 있는 방향은 아래와 같다.
- 우주선은 같은 방향으로 두 번 연속 움직일 수 없다.
최대한 연료를 아끼며 달에 도착하기 위한 연료의 최소값은?

시간 제한

1초

입력

지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 **N, M (2 ≤ N, M ≤ 1000)**이 주어진다
다음 N줄 동안 각 행렬의 원소 값이 주어진다
- 각 행렬의 원소값은 100 이하의 자연수

출력

달 여행에 필요한 최소 연료의 값을 출력

접근법

탑다운 dp로 접근
- 현재위치, cr, cc, 이전 방향 prvDir일 때 소모된 최소 연료 값을 dp배열에 저장
- 즉, 아래로 내려가면서 소모된 가장 작은 연료값을 return 하면서 최종적으로 출발지점 dp에 가장 최소 연료값을 저장함

코드

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


public class Main {
    static int N, M;
    static int[][] map;
    static int[] delR = {0, 1, 1, 1};
    static int[] delC = {0, -1, 0, 1};
    static int[][][] dp;
    static int answer = 1 << 30;

    static int dfs(int cr, int cc, int prvDir) {
        // 달에 도착
        if (cr == N) return 0;

        // 메모 확인
        if (dp[cr][cc][prvDir] != -1) return dp[cr][cc][prvDir];

        int ret = 1 << 30;
        int mr, mc;
        for (int i = 1; i <= 3; i++) {

            // 연속 이동 방지
            if (i == prvDir) continue;

            mr = cr + delR[i];
            mc = cc + delC[i];

            if (mc < 0 || M <= mc) continue;

            ret = Math.min(ret, dfs(mr, mc, i) + map[mr][mc]);
        }

        dp[cr][cc][prvDir] = ret;
        return ret;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N + 1][M];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new int[1010][1010][4];
        for (int[][] d1 : dp) {
            for (int[] d2 : d1) {
                Arrays.fill(d2, -1);
            }
        }

        for (int col = 0; col < M; col++) {
            answer = Math.min(answer, dfs(0, col, 0));
        }

        System.out.println(answer);

        br.close();
    }
}