📙[Algo] 24.05.25 ~ 24.05.26 알고리즘

알고리즘 문제) BOJ 1513. 경로 찾기

• 링크 : https://www.acmicpc.net/problem/1513

문제 요약

• N*M 직사각형 도시에 살고 있음
• (1,1)에서 출발해서 (N,M)으로 가려고 할 때,
  • 이동은 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동
  • 오락실은 번호가 증가하는 순서대로 가야함
• 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.

시간 제한

• 2초

입력

• N M C
  • 모두 50이하 자연수
• 둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다
  • 오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다

출력

• 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력
  • 경로의 개수는 1,000,007로 나눈 나머지를 출력

접근법

• 내가 평소에 풀던 top down dp 구성이랑 달라서 생각보다 버벅거렸던 문제
  • 방문한 오락실 개수마다 경로 개수를 출력해야했다.
• recur 함수
  • row, col → 현재 위치
  • vCnt → 목표로하는 오락실 방문 수 ⇒ 방문할 때마다 1씩 감소
  • prv → 이전 방문한 오락실 번호
• 가지치기 → vCnt가 0 미만인 경우는 오락실을 더 방문했다는 것이므로 return
• 기저조건
  • 목적지에 도착했을 때 vCnt값이 0인경우만 1을 return 시켰다.
• return 값을 누적시켜서 최종적으로 오락실은 vCnt방문했을 때 경로 개수를 반환하도록 했다.
  • 이때, 계산 과정에서 모듈러 연산 적용해야함

코드

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


public class Main {
    static int N, M, C;
    static int[][] map;
    static int[] delR = {1, 0};
    static int[] delC = {0, 1};
    static int[][][][] dp;
    static final int MOD = 1_000_007;

    static int recur(int row, int col, int vCnt, int prv) {

        if (vCnt < 0) return 0;

        if (row == N - 1 && col == M - 1) {
            if (vCnt == 0) return 1;
            else return 0;
        }

        if (dp[row][col][vCnt][prv] != -1) return dp[row][col][vCnt][prv];

        int mr, mc, ret = 0;
        for (int dir = 0; dir < 2; dir++) {
            mr = row + delR[dir];
            mc = col + delC[dir];

            if (N <= mr || M <= mc) continue;

            if (map[mr][mc] > 0) {
                // 오락실일 경우
                if (prv < map[mr][mc]) ret = (ret + recur(mr, mc, (vCnt - 1) % MOD, map[mr][mc]) % MOD) % MOD;
            } else {
                ret = (ret + recur(mr, mc, vCnt, prv) % MOD) % MOD;
            }
        }

        dp[row][col][vCnt][prv] = 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());
        C = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        int r, c;
        for (int i = 1; i <= C; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken()) - 1;
            c = Integer.parseInt(st.nextToken()) - 1;

            map[r][c] = i;
        }

        dp = new int[N + 10][M + 10][C + 10][C + 10];
        for (int[][][] d1 : dp) {
            for (int[][] d2 : d1) {
                for (int[] d3 : d2) {
                    Arrays.fill(d3, -1);
                }
            }
        }

        int ans = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= C; i++) {
            if (map[0][0] > 0) ans = recur(0, 0, i - 1, map[0][0]);
            else ans = recur(0, 0, i, 0);

            sb.append(ans).append(" ");
        }

        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 14420. 양아치 집배원

• 링크 : https://www.acmicpc.net/problem/14220

문제 요약

• 영선이는 N개의 우편물을 N개의 도시에 중복없이 배달해야한다.
• 그러나 영선이는 일을 빨리 마치려고 한 도시를 방문한 후, 다른 도시로 이동 할 때, 빠르게 일을 마칠 수 있다면 방문한 도시를 또 방문했다.
• 영선이의 이동 경로 파악을 위해, 전체 이동이 최소가 되는 경로의 이동 거리를 출력해라

시간 제한

• 1초

입력

• 방문하는 도시 N
  • 1 ≤ N ≤ 500
• N개의 줄에 N개의 원소가 주어짐
  • i번째 줄의 j번째 원소는 i에서 j로 가는데 거리
  • 만약 거리가 0이면 i에서 j로는 이동할 수 없다
  • 두 도시를 잇는 도로가 서로 다른 방향에 대해서 거리가 다를 수 있음
  • 거리값은 1~10만

출력

• 도시를 n번 방문하는데 최소가 되는 경로의 이동거리를 출력
  • 없다면 -1

접근법

• 탑다운 dp + dfs

코드

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

public class Main {
    static int N;
    static ArrayList<Node>[] arr;
    static int[][] dp;

    static class Node{
        int no;
        int dist;

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

    static int recur(int cur, int cnt) {
        if (cnt == N) return 0;

        if (dp[cur][cnt] != -1) return dp[cur][cnt];

        int nxt, nd, ret = 1 << 30;
        for (Node node : arr[cur]) {
            nxt = node.no;
            nd = node.dist;

            ret = Math.min(ret, recur(nxt, cnt + 1) + nd);
        }

        dp[cur][cnt] = ret;
        return ret;
    }


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

        N = Integer.parseInt(br.readLine());

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

        int d;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                d = Integer.parseInt(st.nextToken());

                if (d != 0) {
                    arr[i].add(new Node(j, d));
                }
            }
        }

        // 0번 가상노드 추가
        for (int i = 1; i <= N; i++) {
            arr[0].add(new Node(i, 0));
        }

        dp = new int[N + 10][N + 10];
        for (int[] d1 : dp) {
            Arrays.fill(d1, -1);
        }

        int ans = recur(0, 0);
        if (ans != 1 << 30) System.out.println(ans);
        else System.out.println(-1);

        br.close();
    }
}

 

알고리즘 문제) BOJ 13418. 학교 탐방하기

• 링크 : https://www.acmicpc.net/problem/13418

문제 요약

• 입구 0번부터 건물이 1번~N번 존재
• 입구와 건물, 그리고 건물사이들은 오르막길 또는 내리막길이 존재
• 오르막길을 k번 오를 때, 피로도는 k^2
• 이때, 최소도로 개수로 건물 방문 시 피로도 수치가 최악인 경우와 최선인 경우의 차이를 구하라

시간 제한

• 1초

입력

• 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2)
• 번째 줄부터 M+1개의 줄에는 A, B(1 ≤ A, B ≤ N), C
  • A와 B 건물에 연결된 도로가 있다는 뜻이며, C는 0(오르막길) 또는 1(내리막길)의 값
  • 입구는 항상 1번 건물과 연결되어 있다

출력

• 주어진 조건을 만족하는 최악의 경로에서의 피로도와 최적의 경로 간 피로도의 차이를 출력

접근법

• MST 문제

코드

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

public class Main {
    static int N, M;
    static int[][] graph;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    static int daijk() {
        int ans = 0;
        int v1, v2, c;
        for (int i = 0; i < M + 1; i++) {
            v1 = graph[i][0];
            v2 = graph[i][1];
            c = graph[i][2];

            if (find(v1) == find(v2)) continue;

            union(v1, v2);
            ans += c;
        }

        return ans;
    }

    static void initParent() {
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }
    }

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

        graph = new int[M + 1][3];
        parent = new int[N + 1];

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

            graph[i][0] = v1;
            graph[i][1] = v2;
            graph[i][2] = c == 1 ? 0 : 1;
        }

        // 최선의 경우 찾기
        Arrays.sort(graph, (o1, o2) -> {
            return o1[2] - o2[2];
        });

        initParent();

        int ans1 = daijk();

        // 최악의 경우 찾기
        Arrays.sort(graph, (o1, o2) -> {
            return o2[2] - o1[2];
        });

        initParent();

        int ans2 = daijk();

        System.out.println(ans2 * ans2 - ans1 * ans1);

        br.close();
    }
}

 

알고리즘 문제) BOJ 14442. 벽 부수고 이동하기 2

• 링크 : https://www.acmicpc.net/problem/14442

문제 요약

• N*M 행렬의 맵이 존재
  • 0 : 이동 가능한 공간
  • 1 : 벽(이동X)
• (1,1)에서 (N,M)위치까지 최단 경로로 이동하려고 함
  • 가장 적은 개수의 칸을 지남
    • 시작칸과 끝칸도 포함
• 벽은 K개까지 부수고 이동할 수 있음
• 한 칸에서 이동할 수 있는 칸은 상하좌우 인접 칸이다.
• 최단 거리 구하기

시간 제한

• 2초

입력

• N, M, K
  • 1≤N≤1000
  • 1≤M≤1000
  • 1≤K≤10
• N개의 줄에 M개의 숫자로 맵이 주어짐
  • (1,1)과 (N,M)은 항상 0

출력

• 첫째줄에 최단 거리 출력
  • 불가능하면 -1

접근법

• bfs + 3차원 방문처리

코드

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

public class Main {
    static int N, M, K;
    static int[][] map;
    static boolean[][][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0, K});
        visited[0][0][K] = true;

        int cr, cc, ck, mr, mc, size, dist = 1;
        while (!q.isEmpty()) {

            size = q.size();

            for (int s = 0; s < size; s++) {
                cr = q.peek()[0];
                cc = q.peek()[1];
                ck = q.poll()[2];

                if (cr == N - 1 && cc == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    mr = cr + delR[dir];
                    mc = cc + delC[dir];

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

                    if (map[mr][mc] > 0) {
                        if (ck - 1 < 0) continue;
                        if (visited[mr][mc][ck - 1]) continue;

                        visited[mr][mc][ck - 1] = true;
                        q.offer(new int[]{mr, mc, ck - 1});
                    } else {
                        if (visited[mr][mc][ck]) continue;

                        visited[mr][mc][ck] = true;
                        q.offer(new int[]{mr, mc, ck});
                    }
                }
            }

            dist++;
        }

        return -1;
    }

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

        map = new int[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }

        visited = new boolean[N][M][K + 10];

        System.out.println(bfs());

        br.close();
    }
}

 

알고리즘 문제) BOJ 5971. Meeting Place

• 링크 : https://www.acmicpc.net/problem/5971

문제 요약

• 트리 구조의 농장이 존재
• 각 초원은 다른 초원으로 가는 경로가 존재하며, 부모초원을 가지고 있음(루트노드 초원 1 제외)
• 이때, Bessie와 Jonell은 항상 자신들의 초원의 조상 중 가장 가까운 초원에서 만나기로 함
• 초원은 총 N개가 존재하며, 각 초원의 부모를 나타내는 정보가 주오진다.
• 앞으로 M일동안 Bessie와 Jonell은 매일 만나야 할 곳을 결정해야 한다.
  • k일에 Bessie는 초원 B_k (1 ≤ B_k ≤ N)에 있고, Jonell은 초원 J_k (1 ≤ J_k ≤ N)에 있음

시간 제한

• 1초

입력

• 첫째 줄 : 초원의 수 N, 방목 일정 수 M
  • 1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000
• N-1개 줄 : 각 줄 i에는 부모를 나타내는 정수가 주어짐(초원 2부터 시작)
• 다음 M개의 줄에 k날짜에 Bessie와 Jonell의 위치가 두 정수로 주어짐

출력

• M개의 줄에 매일 Bessie와 Jonell이 만나는 위치 출력

접근법

• LCA 알고리즘 (기본)

코드

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

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

    static void makeTree(int cur, int prv) {
        for (Integer nxt : lst[cur]) {
            if (nxt == prv) continue;

            depth[nxt] = depth[cur] + 1;
            parent[nxt] = cur;
            makeTree(nxt, cur);
        }
    }

    static int findLca(int v1, int v2) {
        if (depth[v1] > depth[v2]) {
            int tmp = v1;
            v1 = v2;
            v2 = tmp;
        }

        while (depth[v1] != depth[v2]) {
            v2 = parent[v2];
        }

        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));
        StringTokenizer st;

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

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

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

        depth = new int[N + 1];

        int p;
        for (int i = 2; i <= N; i++) {
            p = Integer.parseInt(br.readLine());
            lst[p].add(i);
            lst[i].add(p);
        }

        makeTree(1, 0);

        StringBuilder sb = new StringBuilder();
        int v1, v2;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());

            sb.append(findLca(v1, v2)).append("\n");
        }

        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 1766. 문제집

• 링크 : https://www.acmicpc.net/problem/1766

문제 요약

• 1번부터 N번까지 총 N개의 문제가 존재
• 문제 번호는 난이도 순서 → 1번 문제가 가장 쉬운 문제
• 이때 먼저 푸는 것이 좋은 문제가 존대
• 아래 규칙에 따라 문제 풀 순서를 정하려고 함
  • N개의 문제 모두 풀 것
  • 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀 것
  • 가능하면 쉬운 문제부터 풀 것
• 문제 개수와 먼저 푸는 것이 좋은 문제 정보가 주어질 때, 규칙을 만족하며, 풀 문제 순서를 결정해주자

시간 제한

• 2초

입력

• 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다
• M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다
  • A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미

출력

• 풀어야 하는 순서대로 문제 번호를 빈칸을 사이에 두고 출력

접근법

• 위상정렬 알고리즘 사용

코드

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

public class Main {

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

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

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

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

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

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int i = 1; i <= N; i++) {
            if (pCnt[i] == 0) pq.offer(i);
        }

        int cur;
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            cur = pq.poll();

            sb.append(cur).append(" ");

            for (Integer nxt : lst[cur]) {
                pCnt[nxt]--;

                if (pCnt[nxt] == 0) pq.offer(nxt);
            }
        }

        System.out.println(sb);

        br.close();
    }
}