📙 Algorithm Solving/Java
📙[Algo] 24.07.03~07.05 알고리즘
혜덕hyeduck
2024. 7. 5. 13:32
알고리즘 문제) BOJ 5913. 준규와 사과
문제 요약
- 5*5 크기의 과수원이 존재하며, 가장 왼쪾 위 칸은 (1,1), 가장 오른쪽 아래 칸은 (5,5)이다.
- 이때 구역 k개를 제외한 구역에 사과 나무가 하나씩 존재한다
- 준규는 (1,1)에서 사과를 수확, 해빈이는 (5,)에서 수확을 시작
- 이때, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다.
- 준규와 해빈이는 모든 사과를 수확하고 마지막에 같은 칸에서 만나려고 한다.
- 이때, 사과를 수확하는 방법의 수를 구해라
- 수학을 마친 칸으로는 다시 이동하지 않는다.
- 또, 마지막을 제외하고 같은 칸에서 만날 수 없다.
시간 제한
- 1초
입력
- k ( 0 ≤ k ≤ 22, 짝수)
- k개줄에는 사과 나무가 없는 칸의 위치가 주어짐 (i, j)
출력
- 사과를 모두 수확하는 방법의 수를 출력
접근법
- 백트랙킹 돌며, 준규와 해빈이의 위치 (jr,jc) (hr,hc) ,남은 사과나무 개수 remain을 매개변수로 넘겨주었다.
- 이때 둘의 위치가 같을 떄, remain값이 1보다 작을 때 1을 반환시켰고, 그게 아니면 0을 반환 시켰다.
- 마지막칸을 제외하고 같은 칸에서 만날 수 없으므로
- 또한 2중 for문으로 준규와 해빈이의 위치를 이동시키며 나올 수 있는 모든 경우를 탐색
- 이때, 경계 안에서 방문체크와 사과나무가 있는칸(0)만 탐색했고, return값을 ret변수에 누적해서 더했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int K;
static int[][] arr = new int[5][5];
static boolean[][] visited = new boolean[5][5];
static int[] delR = {0, 0, -1, 1};
static int[] delC = {-1, 1, 0, 0};
static int recur(int jr, int jc, int hr, int hc, int remain) {
if (jr == hr && jc == hc) {
// 모든 사과를 수확하고 도착 위치가 같다면
if (remain < 1) {
return 1;
}
else return 0;
}
int ret = 0;
int mjr, mjc, mhr, mhc;
for (int jd = 0; jd < 4; jd++) {
for (int hd = 0; hd < 4; hd++) {
mjr = jr + delR[jd];
mjc = jc + delC[jd];
mhr = hr + delR[hd];
mhc = hc + delC[hd];
if (mjr < 0 || mjc < 0 || mhr < 0 || mhc < 0
|| 5 <= mjr || 5 <= mjc || 5 <= mhr || 5 <= mhc) continue;
if (visited[mjr][mjc] || visited[mhr][mhc]) continue;
if (arr[mjr][mjc] == 1 || arr[mhr][mhc] == 1) continue;
visited[mjr][mjc] = true;
visited[mhr][mhc] = true;
ret += recur(mjr, mjc, mhr, mhc, remain - 2);
visited[mjr][mjc] = false;
visited[mhr][mhc] = false;
}
}
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
K = Integer.parseInt(br.readLine());
int r, c;
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
arr[r][c] += 1;
}
visited[0][0] = true;
visited[4][4] = true;
int ans = recur(0, 0, 4, 4, 25 - K - 2);
System.out.println(ans);
}
}
알고리즘 문제) BOJ 17244. 아맞다우산
문제 요약
- N * M 맵이 존재
- 해당 맵의 값은 다음과 같이 주어진다
- . : 빈칸
- # : 벽 -> 이동 불가
- S : 시작 위치
- E : 도착 위치
- X : 챙겨야할 물건
- S에서 출발하여 물건을 모두 챙기고 E에 가장 빠르게 도착할떄까지 걸리는 시간?
시간 제한
- 1초
입력
- 가로 길이 N과 세로 길이 M
- 3 ≤ N, M ≤ 50
- M개의 줄에 집의 구조가 주어짐
- 챙겨야할 물건은 최대 5개까지 가능
- 집은 언제나 벽으로 둘러싸여 있으며, 도착지는 무조건 하나
출력
- S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력
- 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.
접근법
- bfs + 비트마스킹
- 처음 지도를 입력 받을 때, 문자를 숫자로 변환했다
-
→ -1
- . → 0
- S → 0 & 시작 위치 저장 (sr, sc)
- E → 0 & 도착 위치 저장 (er, ec)
- X → 1부터 하나씩 증가시킴
- 만약 물건이 5개있다면 물건마다 1~5까지 번호가 부여되며, 해당 번호가 지도에 기록된다.
-
- bfs로 S부터 E까지 모든 물건을 챙기고 최단 경로로 이동해야 하므로 bfs알고리즘을 사용
- 이때, 현재까지 어떤 물건을 선택했느냐에 따라 케이스가 나뉘므로
- 방문체크 배열을 3차원으로 선언하여, 현재 위치와 지금까지 선택한 물건 상태값을 기준으로 체크했다.
- 이때 물건을 선택한 상태는 비트마스킹으로 저장
- 어차피 물건은 최대 5개까지만 주어짐
- 이때 물건을 선택한 상태는 비트마스킹으로 저장
- 방문체크 배열을 3차원으로 선언하여, 현재 위치와 지금까지 선택한 물건 상태값을 기준으로 체크했다.
- 이때, 현재까지 어떤 물건을 선택했느냐에 따라 케이스가 나뉘므로
- 만약 물건을 다 선택하고 & 도착지에 도착했다면 그때 걸린 시간을 출력했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] arr;
static int sr, sc, er, ec, idx;
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<>();
visited = new boolean[M][N][1 << 6];
q.offer(new int[]{sr, sc, 0});
visited[sr][sc][0] = true;
int cr, cc, cs, mr, mc, bit, size, time = 0;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cr = q.peek()[0];
cc = q.peek()[1];
cs = q.poll()[2];
if (cr == er && cc == ec && cs == (1 << (idx + 1)) - 2) {
return time;
}
for (int dir = 0; dir < 4; dir++) {
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 0 || mc < 0 || M <= mr || N <= mc) continue;
if (visited[mr][mc][cs]) continue;
if (arr[mr][mc] == 0) {
q.offer(new int[]{mr, mc, cs});
visited[mr][mc][cs] = true;
} else if (arr[mr][mc] > 0) {
bit = cs | (1 << arr[mr][mc]);
q.offer(new int[]{mr, mc, bit});
visited[mr][mc][bit] = true;
}
}
}
time++;
}
return time;
}
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[M][N];
String input;
char ch;
for (int i = 0; i < M; i++) {
input = br.readLine();
for (int j = 0; j < N; j++) {
ch = input.charAt(j);
if (ch == 'S') {
arr[i][j] = 0;
sr = i;
sc = j;
} else if (ch == 'E') {
arr[i][j] = 0;
er = i;
ec = j;
} else if (ch == '#') {
arr[i][j] = -1;
} else if (ch == '.') {
arr[i][j] = 0;
} else if (ch == 'X') {
arr[i][j] = ++idx;
}
}
}
System.out.println(bfs());
}
}
알고리즘 문제) BOJ 1102. 발전소
문제 요약
- 발전소 일부가 고장났다
- 이때 고장나지 않은 발전소를 이용해 고장난 발전소를 고쳐서, 최소 P개의 발전소가 고장나지 않도록하자
- 이때, 발전소를 고치는 최소 비용은?
시간 제한
- 2초
입력
- 발전소 개수 N
- N ≤ 16, 자연수
- N개의 줄에 발전소 i를 통해 j를 재시작할 때 드는 비용(i, j)이 주어진다. → 36이하의 양수
- 그 다음 줄에는 각 발전소가 켜져 있으며 Y, 꺼져있으면 N이 순서대로 주어진다 ex) YNNN
- 마지막 줄에는 P가 주어지며, N이하의 자연수이다
출력
- 정답 출력
- 불가능하면 -1 출력
접근법
- 비트마스킹 + dp문제
- 발전소 상태를 String 값으로 입력 받게 되는데, 나중에 비트로 고장 여부를 확인해야해서 따로 처리
- StringBuilder를 사용해 ‘Y’인 경우 1을 추가했고, ‘N’인 경우 0을 추가했다.
- 이렇게 되면 1번 발전소 상태값이 가장 앞에 가게 되는데, 비트 변환시 1번값이 이 가장 뒤로 가야하므로 reverse() 함수 사용 후, parseInt함수로 2진수 변환했다
- 그러면 현재 발전소 상태값이 2진수형태로 기록
- 또한, 최소 P개의 발전소만 고장나지 않으면 되므로, 앞에서 ‘Y’를 만날때마다 1씩 감소시킨다.
- 이때, P가 음수면 더이상 고칠 필요 없으며 0을 출력,
- 그게 아닐 경우 재귀를 돌려 최소 비용을 구했따.
- 재귀 함수에 매개변수로 remain과 state값을 넘겼고,.
- remain은 고쳐야할 남은 공장 수
- state값은 지금까지 고친 공장 상태값을 기록했다.
- 어떤 공장이 어떤 공장을 고쳤는지에 따라 경우가 나뉘어서, 재귀 안에서 2중 for문을 돌렸다(N이 16이하라 시간 터질 우려 X)
- 외부 for문에서 고장나지 않은 공장만 찾은 후,
- 내부 for문에서 고장난 공장만 선택하게 끔했다.
- 이때, 재귀 호출 시 state값은 비트마스킹으로 고친 공장까지 반영해서 넘겼다.
- 메모이제이션
- dp[remain][state] : 고쳐야 할 공장 수가 remain개 이고, 고친 공장 상태 값이 state일 때 최소 비용
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] arr;
static int min;
static int[][] dp;
static int recur(int remain, int state) {
if (remain == 0) return 0;
if (dp[remain][state] != -1) return dp[remain][state];
int ret = 1 << 30;
for (int i = 0; i < N; i++) {
if ((state & (1 << i)) == 0) continue;
for (int j = 0; j < N; j++) {
if ((state & (1 << j)) != 0) continue;
ret = Math.min(ret, recur(remain - 1, state | (1 << j)) + arr[i][j]);
}
}
dp[remain][state] = 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 int[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());
}
}
String str = br.readLine();
min = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'Y') {
min--;
sb.append("1");
}
else sb.append("0");
}
sb.reverse();
int curBit = Integer.parseInt(sb.toString(), 2);
dp = new int[20][ 1 << 17];
for (int[] d : dp) {
Arrays.fill(d, -1);
}
if (min < 0) System.out.println(0);
else {
int ans = recur(min, curBit);
if (ans == 1 << 30) System.out.println(-1);
else System.out.println(ans);
}
}
}
알고리즘 문제) BOJ 5972. 택배 배송
문제 요약
- N개의 헛간, M개의 양방향 길
- 각각의 길에는 Ci마리의 소가 존재
- 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.
- 현서는 찬홍이에게 가면서 지나가는 길에 소를 만나면 여물을 줘야 할 때, 최소 여물은 얼마일까?
시간 제한
- 1초
입력
- N과 M
- 1 ≤ N ≤ 50,000
- 1 ≤ M ≤ 50,000
- 둘째 줄부터 M+1번째 줄까지 세 개의 정수 Ai, Bi, Ci
- 헛간 Ai, Bi, 소 마리수 Ci
- 1 ≤ Ai ≤ N
- 1 ≤ Bi ≤ N
- Ai != Bi
출력
- 농부 현서가 가져가야 될 최소 여물
접근법
- 다익스트라 알고리즘
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Node>[] lst;
static int[] dist;
static boolean[] visited;
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) {
PriorityQueue<Node> pq = new PriorityQueue<>();
dist[start] = 0;
pq.add(new Node(start, 0));
int cur, nxt, nc;
while (!pq.isEmpty()) {
cur = pq.poll().to;
if (visited[cur]) continue;
visited[cur] = true;
for (Node node : lst[cur]) {
nxt = node.to;
nc = dist[cur] + node.cost;
dist[nxt] = Math.min(dist[nxt], nc);
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;
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<>();
}
int a, b, c;
for (int i = 0; i < M; 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));
}
dist = new int[N + 1];
Arrays.fill(dist, 1 << 30);
visited = new boolean[N + 1];
daijk(1);
System.out.println(dist[N]);
}
}