📙 Algorithm Solving/Java
📙[Algo] 24.08.18 알고리즘
혜덕hyeduck
2024. 8. 18. 17:03
알고리즘 문제) BOJ 16469. 소년 점프
문제 요약
- 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다.
- 뒤늦게 미로에 도착한 악당 무리 3명는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다.
- 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다.
- 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다.
- 악당은 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신
- R*C 크기의 미로가 주어지고, 악당들의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 되는 지점을 마미손에게 알려주자
시간 제한
- 1초
입력
- 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다
- 2 ≤ R, C ≤ 100
- 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다
- 숫자 0은 이동 가능한 길, 1은 벽을 나타낸다
- 그 다음 줄부터 3개의 줄은 악당의 위치(행, 열)를 나타내는 자연수 Xi, Yi가 (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C)주어진다
- 악당들은 위치가 겹치지 않고, 항상 이동 가능한 길에서 출발한다
- 맨 왼쪽 위의 위치는 (1, 1)이다
출력
- 첫째 줄에 한 지점에 세 악당이 모일 때 걸린 시간의 최소 값을 출력
- 둘째 줄에는 그러한 지점의 개수를 출력
- 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력
접근법
- 세 악당이 한 칸에 집합할 수 있는 최단 경로를 찾기 위해 bfs 알고리즘을 사용했다
- 각 악당의 번호 (0 ~ 2)와 각 악당의 위치를 큐에 담았고, 방문체크를 할 때도 각 악당별로 방문체크를 하기 위해 3차원 배열을 사용했다
- 최단 시간을 찾기 위해 bfs를 돌릴 때, 큐 사이즈만큼씩 돌리고나서 time변수를 + 1 해주었다.
- 또한, 3명의 악당이 집합한 개수를 확인하기 위한 2차원 배열 cnt를 선언했고, 각 악당이 이동할 때마다 해당 위치에 존재하는 악당 숫자를 카운팅했다.
- 이때 cnt[row][col]값이 3이 되는 경우, 모든 악당이 모였다는 의미이므로 따로 flag변수를 이용해 true값으로 선언했다.
- 또한, 가능한 경우의 개수도 구해야해서 total변수에 + 1해주었다.
- 한번 큐를 돌고 나서, 만약 flag가 true일 경우, 한 곳에 집합하는 경우를 찾은 것이므로, 그때 까지 소모한 시간 time과 그런 경우의 총 개수인 total을 반환시켰다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] arr;
static int[][] cnt;
static int[][] pos;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int[] bfs() {
Queue<int[]> q = new LinkedList<>();
boolean[][][] visited = new boolean[3][N][M];
for (int i = 0; i < 3; i++) {
q.offer(new int[]{i, pos[i][0], pos[i][1]});
visited[i][pos[i][0]][pos[i][1]] = true;
}
int no, cr, cc, mr, mc, size, time = 0, total = 0;
boolean flag = false;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
no = q.peek()[0];
cr = q.peek()[1];
cc = q.poll()[2];
cnt[cr][cc]++;
if (cnt[cr][cc] == 3) {
flag = true;
total++;
}
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 (visited[no][mr][mc] || arr[mr][mc] == 1) continue;
visited[no][mr][mc] = true;
q.offer(new int[]{no, mr, mc});
}
}
if (flag) return new int[] {time, total};
time++;
}
return new int[]{-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());
arr = new int[N][M];
cnt = new int[N][M];
pos = new int[3][2];
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = input.charAt(j) - '0';
}
}
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
pos[i][0] = Integer.parseInt(st.nextToken()) - 1;
pos[i][1] = Integer.parseInt(st.nextToken()) - 1;
}
int[] ans = bfs();
if (ans[0] == -1) {
System.out.println(-1);
} else {
System.out.println(ans[0]);
System.out.println(ans[1]);
}
}
}
알고리즘 문제) BOJ 28017. 게임을 클리어하자
문제 요약
- 게임은 여러 회차가 존재하며, 무기도 여러가지가 존재한다
- 이때, 한 회차를 클리어 할 때는, 무기를 도중에 바꾸지 않고 게임을 진행한다
- 또한, 여러 회차를 진행할 때, 이전 무기는 또 사용하지 않는다
- 게임 회차별로, 각 무기를 사용할 때 클리어하는 시간도 다르다
- 최선의 무기를 선택해 최대한 빨리 게임을 끝나는 방법을 찾아라
시간 제한
- 1초
입력
- 게임을 몇 회차 하는지 나타내는 수 N과 무기 종류 M이 주어진다
- 2 ≤ N, M ≤ 500
- 둘째줄부터 N개의 줄에 각 무기별 게임을 클리어하는 시간 t1, .. , tN이 주어진다.
- 1 ≤ ti ≤ 1만
출력
- 회차마다 효율적인 무기를 선택하였을 때 총 클리어 시간의 최솟값을 출력
접근법
- dp[cur][pre] : 현재 게임가 cur이고 이전 무기로 pre를 사용했을 때, 얻을 수 있는 최소 비용을 저장
- 각 회차별 이전과 중복되지 않을 무기를 선택했을 때의 모든 케이스를 탐색하고, 중복 케이스 처리를 위해 dp배열을 통해 메모이제이션
- 함수는 게임을 클리어했을 때의 총 소모 시간을 반환하며, 최종적으로 가장 최소 시간을 반환하게 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] arr;
static int[][] dp;
static int dfs(int cur, int pre) {
if (cur == N) return 0;
if (dp[cur][pre] != -1) return dp[cur][pre];
int ret = 1 << 30;
for (int i = 1; i <= M; i++) {
if (pre == i) continue;
ret = Math.min(ret, dfs(cur + 1, i) + arr[cur][i]);
}
dp[cur][pre] = 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 + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N][M + 1];
for (int[] d : dp) {
Arrays.fill(d, -1);
}
int ans = dfs(0, 0);
System.out.println(ans);
}
}