📙 Algorithm Solving/Java
📙[Algo] 24.09.01 알고리즘
혜덕hyeduck
2024. 9. 1. 15:07
알고리즘 문제) BOJ 16197. 두 동전
문제 요약
- N*N 보드와 4개의 버튼이 존재
- 보드 위에는 동전이 하나씩 놓여져 있으며, 두 위치는 다르다
- 버튼은 왼쪽, 오른쪽, 위, 아래 4가지가 존재
- 이때, 버튼을 누르면 해당 방향으로 두 동전이 동시에 이동한다
- 동전이 이동하려는 칸이
- 벽 → 이동 X
- 경계 밖 → 바깥으로 떨어짐
- 그 외에는 해당 위치로 이동(이미 동전이 있는 경우에도 이동)
- 동전이 이동하려는 칸이
- 두 동전 중 하나만 보드에서 떨어뜨리려면 최소 몇 번 클릭??
시간 제한
- 2초
입력
- 보드 세로 크기 N, 가로 크기 M
- 1 ≤ N, M ≤ 20
- N개의 줄에 보드 상태가 주어짐
- o : 동전
- . : 빈칸
- # : 벽
- 동전의 개수는 항상 2개
출력
- 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력
- 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력
접근법
- 두 동전을 동시에 이동시켜야 하기 때문에, 하나의 상태를 두 동전의 위치로 정의했다.
- 즉, 큐에 담을 때와 방문 체크할 때, 두 동전의 위치를 한 번에 기록 했다
- q.offer(new int[] {동전1의 row값, 동전1의 col값, 동전2의 row값, 동전2의 col값})
- visited[{동전1의 row값][동전1의 col값][{동전2의 row값][동전2의 col값] = true;
- 또한, 버튼의 최소 클릭 수를 구해야하기 때문에 → 최단 경로 알고리즘인 BFS를 사용했다.
- 이때, 버튼 클릭 수를 알아내야 하므로, 현재 큐에 담긴 것은 버튼을 total개 눌렀을 때 나올 수 있는 모든 상황이므로, 현재 큐의 size만큼 bfs를 돌리도록 했다.
- 이후 size만큼 bfs가 끝났다면, 버튼 클릭 수 total + 1을 했다.
- 이때, 버튼 클릭 수를 알아내야 하므로, 현재 큐에 담긴 것은 버튼을 total개 눌렀을 때 나올 수 있는 모든 상황이므로, 현재 큐의 size만큼 bfs를 돌리도록 했다.
- 문제에서, 경계를 나가면 동전을 떨어뜨린 것이라고 정의했기 때문에
- 처음 남은 동전수 remain을 2로 초기화 한 뒤, 각 동전을 동시에 이동 시켰을 때 경계를 벗어나면 remain -= 1을 했다.
- 이때, remain이 0인 경우 모두 이탈한 것이므로, 해당 케이스는 더이상 진행하지 않고,
- remain이 1인 경우 동전 하나만 남은 것이므로 바로 현재 버튼 클릭 수 total을 반환했다.
- remain이 2라면 아직 두 동전 모두 보드위에 있는 것이므로, 다음 케이스를 살 필 수 있도록 큐에 담았다
- 단, 동전이 이동하려는 위치가 벽인 경우 이동 위치를 다시 현재위치로 갱신했다.
- 또한, 두 동전의 이동할 위치가 이미 살펴봤던 경우(visited)에는 해당 케이스는 패스하고, 그게 아니라면 큐에담고 방문체크했다.
- 처음 남은 동전수 remain을 2로 초기화 한 뒤, 각 동전을 동시에 이동 시켰을 때 경계를 벗어나면 remain -= 1을 했다.
- 즉, 큐에 담을 때와 방문 체크할 때, 두 동전의 위치를 한 번에 기록 했다
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static char[][] board = new char[30][30];
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static ArrayList<int[]> coins = new ArrayList<>();
static boolean[][][][] visited = new boolean[30][30][30][30];
static int move() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{coins.get(0)[0], coins.get(0)[1], coins.get(1)[0], coins.get(1)[1]});
visited[coins.get(0)[0]][coins.get(0)[1]][coins.get(1)[0]][coins.get(1)[1]] = true;
int cr1, cc1, mr1, mc1, cr2, cc2, mr2, mc2, remain, size, total = 1;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cr1 = q.peek()[0];
cc1 = q.peek()[1];
cr2 = q.peek()[2];
cc2 = q.poll()[3];
for (int dir = 0; dir < 4; dir++) {
// 두 동전 동시에 이동
remain = 2;
mr1 = cr1 + delR[dir];
mc1 = cc1 + delC[dir];
mr2 = cr2 + delR[dir];
mc2 = cc2 + delC[dir];
// 경계밖을 떠났으므로 해당 동전은 탈락
if (mr1 < 0 || mc1 < 0 || N <= mr1 || M <= mc1) remain--;
if (mr2 < 0 || mc2 < 0 || N <= mr2 || M <= mc2) remain--;
// 동전 모두 탈락
if (remain == 0) continue;
// 동전 하나만 살아남음
if (remain == 1) return total;
// 동전 둘다 살아남음
if (remain == 2) {
// 동전1이 벽을 만났다면 현재위치로 고정
if (board[mr1][mc1] == '#') {
mr1 = cr1;
mc1 = cc1;
}
// 동전2가 벽을 만났다면 현재위치로 고정
if (board[mr2][mc2] == '#') {
mr2 = cr2;
mc2 = cc2;
}
// 이미 방문한 케이스라면 pass
if (visited[mr1][mc1][mr2][mc2]) continue;
// 현재 두 동전의 위치를 큐에 담고 방문처리
q.offer(new int[]{mr1, mc1, mr2, mc2});
visited[mr1][mc1][mr2][mc2] = true;
}
}
}
// 버튼 클릭
total++;
// 10번 초과한 경우 무조건 -1 반환
if (total > 10) return -1;
}
return -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());
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = input.charAt(j);
if (board[i][j] == 'o') coins.add(new int[]{i, j});
}
}
int ret = move();
System.out.println(ret);
}
}
알고리즘 문제) BOJ 3671. 산업 스파이의 편지
문제 요약
- 종이 조각을 적절히 배치해서 소수가 되는 경우가 몇 개이지 알려주실 수 있나요?
시간 제한
- 1.5초
입력
- 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200)
- 각 테스트 케이스는 한 줄로 이루어져 있고, 종이조각에 쓰여 있는 수가 공백없이 주어진다
- 종이조각의 수는 적어도 1개, 많아야 7개
- 종이 조각을 적절히 배치해서 만든 숫자가 0으로 시작할 때, 앞에있는 0을 지운 수가 같으면 같은 숫자
출력
- 각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력
접근법
- 주어지는 숫자 조각수가 최대 7조각이므로 등장할 수 있는 최대 숫자는 9999999이다.
- 따라서 미리 에라토스테네스체로 1~9999999까지 소수판정 배열을 생성했다 ⇒ isPrime
- 이후, 각 테스트케이스별로 가능한 모든 숫자조합을 체크하면서 소수인 개수를 찾아야 한다.
- 모든 숫자 조합을 찾기 위한 recur 함수를 만들었다 ⇒ 대략 최대 6^7까지 나올 수 있으므로, 완전 탐색이 가능하다
- 선택한 경우 → 매개변수로 그다음 자릿수(cur+1)와 현재까지 만든 숫자(num * 10 + 현재 숫자)를 넘겼다.
- 선택하지 않은 경우 → 더 이상 숫자 생성을 멈추므로 바로 cur을 len으로 갱신했다.
- 만약 cur가 len인 경우 ⇒ 해당 숫자가 소수라면 set에 담았다
- 중복없이 만들 수 있는 소수 개수를 구해야하므로 set 자료구조 활용
- 마지막으로 set의 크기를 출력했다
코드
import java.io.*;
import java.util.*;
public class Main {
static boolean[] isPrime = new boolean[10_000_000];
static String input;
static int len;
static boolean[] visited = new boolean[20];
static Set<Integer> set = new TreeSet<>();
// 소수판정 배열 만들기
static void findPrime() {
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i <= 9999999; i++) {
if (!isPrime[i]) continue;
for (long j = (long) i * i; j <= 9999999; j += i) {
isPrime[(int) j] = false;
}
}
}
static void recur(int cur, int num) {
if (cur == len) {
if (isPrime[num]) {
set.add(num);
}
return;
}
// 선택
for (int i = 0; i < len; i++) {
if (visited[i]) continue;
visited[i] = true;
recur(cur + 1,
num * 10 + input.charAt(i) - '0');
visited[i] = false;
}
// 선택 X
recur(len, num);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 소수판정 배열 만들기
findPrime();
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
input = br.readLine();
len = input.length();
recur(0, 0);
sb.append(set.size()).append("\\n");
set.clear();
}
System.out.println(sb);
}
}