📙 Algorithm Solving/Java

📙[Algo] 24.05.14 알고리즘

혜덕hyeduck 2024. 5. 14. 17:01

알고리즘 문제) BOJ 22116. 창영이와 퇴근

문제 요약

  • 창영이의 퇴근길은 N×N 크기의 격자로 표현
    • 각 칸에는 해당 지역의 높이가 적혀있음
    • 인접칸 높이차의 절대값 = 경사
  • A1,1에서 출발하여 AN,N까지 이동할 계획
    • 상하좌우 인접 한 칸씩 이동 가능
  • 지날 수 있는 최대 경사의 최솟값 찾아보자

시간 제한

  • 2초

입력

  • 첫째줄 ; 격자 크기 N
    • 1 ≤ N ≤ 1,000
  • 둘째줄부터 N개 줄에 걸쳐 각 격자의 높이 정보가 주어짐
    • 첫 번째로 주어지는 값이 A1,1이고, 마지막으로 주어지는 값이 AN,N
    • 1 ≤ Ar,c ≤ 1,000,000,000

출력

  • A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력

접근법

  • dfs+dp로 풀면 3차원 배열이 필요하기때문에 메모리초과가뜬다.
  • 그래서 2차원을 1차원 노드로 펼치고, 각 경사로를 두 노드간 거리로 생각한 그래프를 만든후 다익스트라 알고리즘으로 접근했다.
    • 기존 익숙한 방법으로는 dist배열에 해당 노드까지의 거리를 저장했다면, 이번에는 거리가 아닌 해당 노드까지 최대경사값으로 갱신했다.
    • 경사크기가 가장 작은 순으로 pq에 담으면서, 최종적으로 dist배열 값에는 해당 노드까지 갈때 최대 경사값의 최솟값이 저장되도록 했다.

코드

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


public class Main {
    static int N;
    static int[][] arr;
    static ArrayList<Node>[] lst;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static boolean[] visited;
    static int[] dist;

    // 기존 dp+dfs로 접근하면 메모리 초과 뜸 -> 각 칸을 노드라고 생각하고 최단경로 알고리즘으로 풀기

    static class Node implements Comparable<Node> {
        int no;
        int d;

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

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

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


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

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : lst[cur]) {
                nxt = node.no;
                nd = Math.max(dist[cur], node.d);

                dist[nxt] = Math.min(dist[nxt], nd);
                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }

    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];
        lst = new ArrayList[N * N + 1];
        for (int i = 0; i < N * N + 1; i++) {
            lst[i] = new ArrayList<>();
        }
        visited = new boolean[N * N + 1];
        dist = new int[N * N + 1];
        Arrays.fill(dist, 1 << 30);

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

        // 2차원을 1차원으로 펼치기 -> row*N+col+1
        // 인접칸 거리(경사 크기) 저장
        int from, to, mrow, mcol, dst;
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                from = row * N + col + 1;

                for (int d = 0; d < 4; d++) {
                    mrow = row + delR[d];
                    mcol = col + delC[d];

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

                    to = mrow * N + mcol + 1;

                    dst = Math.abs(arr[row][col] - arr[mrow][mcol]);

                    lst[from].add(new Node(to, dst));
                }
            }
        }

        daijk(1);

        System.out.println(dist[N * N]);

        br.close();
    }
}

 

알고리즘 문제) BOJ 21758. 꿀 따기

문제 요약

  • 좌우로 펼쳐진 N개의 장소를 두고, 각 칸에는 꿀의 양이 적혀있다.
  • N개의 장소에서 서로 다른 두 곳에 벌을 한 마리씩 두고, 다른 한 곳에는 벌통을 둔다.
  • 두 마리 벌은 벌통으로 직진으로 날아가면서 지나가는 모든 칸의 꿀을 딴다.
    • 벌이 시작한 장소에서는 꿀을 딸 수 없다.(다른 벌이 있는 곳도 포함)
    • 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양만큼 꿀을 딴다.
      • 벌통이 있는 장소도 포함
  • 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성

시간 제한

  • 1초

입력

  • 장소의 수 N
    • 3 ≤ N ≤ 10만
  • 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다(N개)
    • 1 ≤ 꿀의 양 ≤ 1만

출력

  • 가능한 최대의 꿀의 양을 출력

접근법

  • N이 10만 개 ⇒ for문은 1개만 사용 가능
  • 꿀의 총합을 구할 때 일일이 합계를 구하면 최악의 경우 10만*(10만-2)로 시간초과 뜨므로 누적합 배열을 만들어서 사용한다. ⇒ →누적 prefix 배열, ←누적 suffix 배열 두가지
  • 꿀벌과 꿀통의 위치는 다음과 같은 세가지 형태가 나옴
    • 꿀벌2마리 - 꿀통
    • 꿀통 - 꿀벌 2마리
    • 꿀벌 - 꿀통 - 꿀벌
  • 꿀벌2마리 - 꿀통인 경우
    • 꿀통은 N칸에 위치했을 때 꿀을 최대로 먹을 수 있음
    • 꿀벌1은 1칸에 위치해야 꿀을 최대로 먹음
    • 꿀벌2는 2칸에 위치했을 때 꿀을 최대로 먹을 수 있으나, 해당 칸이 꿀이 매우 큰 상황이라면 꿀벌1이 먹을 수 있는 꿀에 영향을 주므로,
      • N-2칸 for문을 돌며 꿀벌2가 해당 위치에 있을 때 꿀벌1,2가 먹을 수 있는 꿀의 최대양 갱신
  • 꿀통 - 꿀벌2마리인 경우 ⇒ 위 케이스와 비슷하게 푼다.
  • 꿀벌 - 꿀통 - 꿀벌인 경우
    • 꿀벌이 1칸, N칸에 위치 시켰을 때 최대로 먹을 수 있는 꿀의 양 구하기
    • prefix[꿀통위치] - prefix[0] + suffix[꿀통위치] - suffix[N] 가 최대인 값 찾기

코드

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


public class Main {
    static int N;
    static int[] arr;
    static int[] prefix;
    static int[] suffix;

    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 + 1];
        prefix = new int[N + 1];
        suffix = new int[N + 2];

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

        for (int i = 1; i <= N; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }

        for (int i = N; i >= 1; i--) {
            suffix[i] = suffix[i + 1] + arr[i];
        }

        int answer = 0, sum;

        // 꿀벌 - 꿀통 - 꿀벌
        for (int i = 2; i <= N - 1; i++) {
            sum = prefix[i] - prefix[1] + suffix[i] - suffix[N];
            answer = Math.max(answer, sum);
        }

        // 꿀벌1,2 - 꿀통
        for (int i = 2; i < N; i++) {
            sum = prefix[N] - prefix[1];
            sum += (prefix[N] - prefix[i]) - arr[i];
            answer = Math.max(answer, sum);
        }

        // 꿀통 - 꿀벌1,2
        for (int i = N - 1; i >= 2; i--) {
            sum = suffix[1] - suffix[N];
            sum += (suffix[1] - suffix[i]) - arr[i];
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);

    }
}