📙[Algo] 24.09.03 ~ 24.09.04 알고리즘

알고리즘 문제) BOJ 5944. Apple Delivery

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

문제 요약

• C개의 길과 P개의 목초지가 존재
• 이때, 각 길에는 거리비용이 존재
• PB에서 시작해 PA1와 PA2 목초지로 방문하려고 할 때, 이동해야할 최소 거리는?

시간 제한

• 2초

입력

• C, P, PB, PA1, PA2
  • 1 ≤ C ≤ 20만
  • 1 ≤ P ≤ 10만
  • 모든 거리의 합은 20억을 초과X
• C개의 줄에 두 목초지 번호와 그 사이 거리가 주어짐

출력

• 두 목초지를 방문할 때 이동할 최소 거리는?

접근법

• PB에서 PA1과 PA2 방문을 위한 최소 경로를 구해야하므로 총 2가지 경로가 있을 수 있다
  • PB → PA1 → PA2
  • PB → PA2 → PA1
• 따라서, PB ~ PA1 / PB ~ PA2 / PA1 ~ PA2 총 3가지의 최단 경로를 구할 필요가 있다.
• 최단 경로 알고리즘으로 다익스트라를 사용했고, 출발지가 PB인 경우, PA1인 경우 2가지를 고려했다.
  • PB를 출발지로 결정했을 때, PB~PA1과 PB~PA2 거리를 구하고, PA1을 출발지로 결정했을 때 PA1 ~ PA2의 거리를 구한 뒤,
  • min(PB~PA1 + PA1~PA2, PB~PA2 + PA1~PA2) 중 최소 거리를 구했다.

코드

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

public class Main {
    static int C, P, PB, PA1, PA2;
    static int[] dist;
    static boolean[] visited;
    static ArrayList<Node>[] lst;
    static PriorityQueue<Node> pq = new PriorityQueue<>();

    static class Node implements Comparable<Node> {
        int to;
        int cost;

        Node(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node node) {
            return this.cost - node.cost;
        }
    }

    static void daijk(int start) {
        Arrays.fill(dist, 1 << 30);
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        int cur, nxt;
        while (!pq.isEmpty()) {
            cur = pq.poll().to;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : lst[cur]) {
                nxt = node.to;
                dist[nxt] = Math.min(dist[nxt], dist[cur] + node.cost);
                pq.offer(new Node(nxt, dist[nxt]));
            }
        }

        Arrays.fill(visited,false);
        pq.clear();
    }

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

        st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        PB = Integer.parseInt(st.nextToken());
        PA1 = Integer.parseInt(st.nextToken());
        PA2 = Integer.parseInt(st.nextToken());

        dist = new int[P + 1];
        visited = new boolean[P + 1];
        lst = new ArrayList[P + 1];
        for (int i = 0; i < P + 1; i++) {
            lst[i] = new ArrayList<>();
        }

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

            lst[a].add(new Node(b, c));
            lst[b].add(new Node(a, c));
        }

        // PB -> PA1 -> PA2
        // PB -> PA2 -> PA1

        int d1, d2, d3;
        daijk(PB);
        // PB <-> PA1
        d1 = dist[PA1];
        // PB <-> PA2
        d2 = dist[PA2];

        daijk(PA1);
        // PA1 <-> PA2
        d3 = dist[PA2];

        System.out.println(Math.min(d1 + d3, d2 + d3));
    }
}

 

알고리즘 문제) BOJ 2146. 다리 만들기

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

문제 요약

• N*N크기의 이차원 평면에 여러 섬들이 존재한다
• 이때, 바다에 가장 짧은 다리를 놓아 두 섬을 연결하려고 한다. ⇒ 칸의 수가 가장 작은 다리를 의미
• 지도가 주어졌을 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾아라

시간 제한

• 2초

입력

• 지도 크기 N
• N개의 줄에 지도 정보가 주어짐
  • 0 : 바다
  • 1 : 육지
  • 항상 두 개이 상의 섬이 있는 데이터만 주어진다

출력

• 가장 짧은 다리 길이 출력

접근법

• 먼저 dfs를 통해 섬마다 번호를 붙였다.
  • 이때, 각 섬들의 좌표를 미리 큐에 담아뒀다 → 나중에 bfs 때 사용
• 이후 섬들 사이 최단 경로를 구하기 위해 bfs를 사용했다.
  • 여기서 방문체크는 각 섬들번호와 좌표를 기준으로 3차원 배열로 체크했다.
    • 다른 섬에서 출발한 경로를 또 방문하지 못하는 경우를 막기 위해
    • 즉, 출발지 섬의 번호를 함께 기록했다
  • 좌표를 이동하면서, 출발지 섬 번호(no)와 다른 섬 번호를 만났을 때 거리를 반환 했다

코드

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

public class Main {
    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static boolean[][][] visited2;
    static Queue<int[]> q = new LinkedList<>();
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    // 섬마다 번호 붙이기
    static void dfs(int row, int col, int no) {
        visited[row][col] = true;
        arr[row][col] = no;
        q.offer(new int[]{row, col, no});
        
        int mrow, mcol;
        for (int dir = 0; dir < 4; dir++) {
            mrow = row + delR[dir];
            mcol = col + delC[dir];

            if (mrow < 0 || mcol < 0 || N <= mrow || N <= mcol
                    || visited[mrow][mcol] || arr[mrow][mcol] == 0) continue;

            dfs(mrow, mcol, no);
        }
    }

    // 섬끼리 최단 경로 찾기
    static int bfs() {

        int ans = 1 << 30, cr, cc, no, mr, mc, size, dist = 0;
        while (!q.isEmpty()) {
            size = q.size();

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

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

                    if (mr < 0 || mc < 0 || N <= mr || N <= mc) continue;
                    if (visited2[mr][mc][no]) continue;
                    if (arr[mr][mc] != 0 && arr[mr][mc] != no) return dist;

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

            dist++;
        }

        return ans;
    }

    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 int[N][N];
        visited = new boolean[N][N];

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

        // 섬마다 번호 붙이기
        int idx = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] || arr[i][j] == 0) continue;

                dfs(i, j, idx++);
            }
        }

        visited2 = new boolean[N][N][idx];
        int ret = bfs();

        System.out.println(ret);
    }
}

 

알고리즘 문제) BOJ 21923. 곡예 비행

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

문제 요약

• 모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다
• 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 시작해야 한다
• 상승 비행 중에는 앞 또는 위로만 이동할 수 있고, 하강 비행 중에는 앞 또는 아래로만 이동할 수 있다
• 구역마다 점수가 적혀있을 때, 얻을 수 있는 최대 점수를 구해라

시간 제한

• 1초

입력

• 전체 구역의 세로 길이 N, 가로 길이 M
  • 1 ≤ N, M ≤ 1000
• 구역 정보가 주어진다 → 각 칸에는 점수가 적혀 있다.
  • -10000 ≤ 점수 ≤ 10000

출력

• 얻을 수 있는 최대 점수를 출력

접근법

• 현재 좌표 row, col과 하강 시작 여부 change를 매개변수로 넘기며 재귀 함수를 돌렸다
• 문제에서 처음에 무조건 상승으로 시작하라고 했으므로, 시작 위치 N-1, 0과 change값은 0으로 시작했다
  • 아직 상승 중이라면 상승 이동을 시켰고, 동시에 이동하려는 칸의 점수를 반환값에 함께 더했다.
  • 만약, 현재 위치에서 하강을 시도한다면 change값은 1로 수정하고, 현재 위치의 점수를 더해주었다.
  • 하강 중이라면 계속 하강 이동을 시키며, 이동하려는 칸의 점수를 함께 더했다.
  • 만약 도착 지점에 도달했다면 (N-1, M-1) 처음 시작위치를 반환했다 ⇒ 시작위치를 더해주지 않았기 때문(혹은 마지막 정답 변수 ret에 시작위치를 더해줘도 된다.)
• 시간복잡도 분석
  • 완탐으로 접근하면 나올 수 있는 케이스가 최대 3^(N*M)이 된다
  • 따라서 dp배열에 메모이제이션을 하며, 최적화를 진행해야 한다.
    • dp배열에는 현재 상태(row,col,change값)에서의 최댓값을 저장하게 된다.
  • 최적화를 진행하면 중복 계산을 피하게 되므로 O(N*M)으로 줄일 수 있다.

코드

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

public class Main {
    static int N, M; // 세로, 가로
    static int[] delR = {-1, 0, 0, 1}; // 0~1 : 상승, 2~3 : 하강
    static int[] delC = {0, 1, 1, 0};
    static int[][] arr;
    static int[][][] dp;

    static int recur(int row, int col, int change) {
        if (row == N - 1 && col == M - 1 && change == 1) return arr[N - 1][0];

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

        int ret = Integer.MIN_VALUE, mrow, mcol;
        // 상승이라면
        if (change == 0) {
            for (int dir = 0; dir <= 1; dir++) {
                mrow = row + delR[dir];
                mcol = col + delC[dir];

                if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol) continue;

                // 상승유지
                ret = Math.max(ret, recur(mrow, mcol, change) + arr[mrow][mcol]);
            }
            // 하강으로 바꾸기
            ret = Math.max(ret, recur(row, col, 1) + arr[row][col]);
        }
        // 하강이라면
        else if (change == 1) {
            for (int dir = 2; dir <= 3; dir++) {
                mrow = row + delR[dir];
                mcol = col + delC[dir];

                if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol) continue;

                // 하강유지
                ret = Math.max(ret, recur(mrow, mcol, change) + arr[mrow][mcol]);
            }
        }

        dp[row][col][change] = 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());

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

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

        int ret = recur(N - 1, 0, 0);
        System.out.println(ret);
    }
}