📙[Algo] 24.09.01 알고리즘

알고리즘 문제) BOJ 16197. 두 동전

• 링크 : https://www.acmicpc.net/problem/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을 했다.
  • 문제에서, 경계를 나가면 동전을 떨어뜨린 것이라고 정의했기 때문에
    • 처음 남은 동전수 remain을 2로 초기화 한 뒤, 각 동전을 동시에 이동 시켰을 때 경계를 벗어나면 remain -= 1을 했다.
      • 이때, remain이 0인 경우 모두 이탈한 것이므로, 해당 케이스는 더이상 진행하지 않고,
      • remain이 1인 경우 동전 하나만 남은 것이므로 바로 현재 버튼 클릭 수 total을 반환했다.
      • remain이 2라면 아직 두 동전 모두 보드위에 있는 것이므로, 다음 케이스를 살 필 수 있도록 큐에 담았다
        • 단, 동전이 이동하려는 위치가 벽인 경우 이동 위치를 다시 현재위치로 갱신했다.
        • 또한, 두 동전의 이동할 위치가 이미 살펴봤던 경우(visited)에는 해당 케이스는 패스하고, 그게 아니라면 큐에담고 방문체크했다.

코드

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. 산업 스파이의 편지

• 링크 : https://www.acmicpc.net/problem/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);
    }
}