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