📙[Algo] 24.02.28~24.02.29 알고리즘

알고리즘 문제) BOJ 25824. 빠른 오름차순 메시지 전달

• 링크 : https://www.acmicpc.net/problem/25824

문제 요약

• 선생님 1명, 학생 12명(1번~12번)
  • 학생들은 두 명씩 집단을 이룸
    • 1번부터 번호순으로 두 명씩 하나의 친구 집단에 포함 됨
      • 친구 집단 1 : {1번, 2번}
      • 친구 집단 2 : {3번, 4번}…
• 선생님이 친구 집단 1에 메시지를 전달했을 때, 메시지를 받은 1번 또는 2번 학생은 같은 친구 집단의 2번 또는 1번 학생에게 메시지를 전달받고, 친구 집단2의 1번 또는 2번 학생한테 메시지를 전달한다.
  • 이 과정을 반복해서 친구 집단 1에서 ~ 친구 집단 6까지 메시지를 전달할 때 걸리는 최소 시간 출력하기
  • 첫 번째 학생이 선생님으로부 메시지를 받는 데 걸리는 시간은 0이다.

시간 제한

• 3초

입력

• 첫 번째 줄부터 열두 개의 줄에 걸쳐 메시지를 전달하는데 걸리는 시간이 주어짐
  • (i,j) → 학생 i가 학생 j에 전달하는데 걸리는 시간
    • 1≤걸리는 시간 ≤ 1000
    • (i,j) == (j,i)
    • 자기 자신한테는 0

출력

• 친구 집단 1부터 친구 집단 6까지 순서대로 12명의 친구에게 메시지를 전달하는데 걸리는 시간?

접근법

{1, 2} {3, 4} {5, 6} {7, 8}….

1 → 2 → 3 → 4 …

1 → 2 → 4 → 3 …

2 → 1 → 3 → 4 …

2 → 1 → 4 → 3 …

나올 수 있는 모든 경우의 수

22222222222*2 = 2^12 = 4096 가지

집단 번호 1부터 시작 → 2명씩 지날때마다 집단 번호 증가

→ 번호 탐색은 집단 번호 2 -2 ~집단번호2-2+1까지

1 : {0, 1}

2 : {2, 3}

3 : {4, 5}

4 : {6, 7}

5 : {8, 9}

6 : {10, 11}

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr = new int[12][12];
    static int[] selected = new int[12];
    static boolean[] visited = new boolean[12];
    static int answer = Integer.MAX_VALUE;

    static void recur(int cur, int total, int groupNo) {

        if (cur == 12) {
            int sum = 0;
            for (int i = 0; i < 11; i++) {
                sum += arr[selected[i]][selected[i + 1]];
            }

            answer = Math.min(answer, sum);

            return;
        }

        for (int i = groupNo * 2 - 2; i < groupNo * 2; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            selected[cur] = i;

            if (total == 2) {
                recur(cur + 1, 1, groupNo + 1);
            } else {
                recur(cur + 1, total + 1, groupNo);
            }

            visited[i] = false;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        for (int i = 0; i < 12; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 12; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recur(0, 1, 1);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 5568. 카드 놓기

• 링크 : https://www.acmicpc.net/problem/5568

문제 요약

• 카드 n장
  • 4≤n≤10
  • 각 카드에는 1~99이하의 정수가 적혀 있음
• 카드 중 k장을 선택하고, 나란히 정수를 만들려고 함
  • 2≤k≤4
• 만들 수 있는 정수는 총 몇 가지일까?

시간 제한

• 1초

입력

• N
• K
• 셋째 줄부터 N개의 줄에 카드에 적힌 수가 주어짐

출력

• 만들 수 있는 정수의 개수

접근법

• NPK를 하고 카드끼리 조합하는 경우를 생각한다.
  • 이때, 중복된 숫자가 나올 수 있음
    • 21,1,2 를 뽑았을 때 21/2/1 랑 2/1/21이랑 같음 ⇒ set에 담자!
• 순서가 있기 때문에 조합이 아닌 순열

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static int[] cards;
    static boolean[] visited;
    static int[] selected;
    static Set<String> set = new TreeSet<>();

    static void recur(int cur) {

        if (cur == K) {

            String str = "";
            for (int i = 0; i < K; i++) {
                str += selected[i];
            }

            set.add(str);

            return;
        }

        for (int i = 0; i < N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            selected[cur] = cards[i];

            recur(cur + 1);

            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(br.readLine());
        }

        visited = new boolean[N];
        selected = new int[K];

        recur(0);

        bw.write(String.valueOf(set.size()));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2580. 스도쿠

• 링크 : https://www.acmicpc.net/problem/2580

문제 요약

• 각각의 가로줄, 세로줄에는 1~9까지 숫자가 한 번씩만 나타날 것
• 굵은 선으로 구분되는 3*3 정사각형 안에도 1~9까지 숫자가 한 번씩만 나타날 것
• 스도쿠 판에 쓰여 있는 숫자 정보가 주어질 때 위 규칙에 따라 채워진 최종 모습 출력 하기

시간 제한

• 292ms(0.292초..?)

입력

• 아홉에 걸쳐 한 줄에 9개씩 숫자가 주어짐
  • 빈칸은 0이 주어짐
  • 규칙대로 채울 수 있는 경우만 입력으로 주어진다.

출력

• 최종 모습 출력
  • 여러 개면 하나만 출력

접근법

• 같은 행에 같은 숫자가 중복되면 안 됨 (1~9)
• 같은 열에 같은 숫자가 중복되면 안 됨 (1~9)
• (0,0), (0,3), (0,6), (3,0) (3,3) (3,6) (6,0) (6,3) (6,6) 에서 row, col에 +3씩한 범위 안에 같은 숫자가 중복되면 안 됨
• 12095 문제 코드를 참고해서 풀어야한다.
• 배열을 돌면서 입력값이 0인 곳만 탐색한다.
  • 같은 행 체크
  • 같은 열 체크
  • 내각 속한 3*3 사각형 범위 내 체크
  • 방문하지 않은 숫자만 입력 하고 방문 처리
• 만약 숫자를 채우는게 불가능 할 경우 가지치기 ⇒ return
• 숫자를 모두 탐색한 경우 → 출력하고 끝내기

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int[][] map = new int[9][9];
    static boolean[][] rowCheck = new boolean[9][10];
    static boolean[][] colCheck = new boolean[9][10];
    static boolean[][] squareCheck = new boolean[9][10];
    static StringBuilder sb = new StringBuilder();

    static int square(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }

    static void recur(int row, int col) {

        if (col == 9) {
            col = 0;
            row++;
        }

        if (row == 9) {

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j] + " ");
                }
                sb.append("\\n");
            }
            System.out.println(sb);
            System.exit(0);
        }

        if (map[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (!rowCheck[row][i] && !colCheck[col][i] && !squareCheck[square(row, col)][i]) {
                    map[row][col] = i;
                    rowCheck[row][i] = colCheck[col][i] = squareCheck[square(row,col)][i] = true;

                    recur(row, col + 1);
                    map[row][col] = 0;
                    rowCheck[row][i] = colCheck[col][i] = squareCheck[square(row,col)][i] = false;
                }
            }
            return;
        }

        recur(row, col + 1);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] != 0) {
                    rowCheck[i][map[i][j]] = true;
                    colCheck[j][map[i][j]] = true;
                    squareCheck[square(i,j)][map[i][j]] = true;
                }
            }
        }

        recur(0,0);

        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1799. 비숍

• 링크 : https://www.acmicpc.net/problem/1799

문제 요약

• 비숍 : 대각선 방향으로 움직일 수 있음
• 비숍을 놓을 수 없는 칸이 있다고 할 때, 비숍끼리 서로 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수는?

시간 제한

• 10초

입력

• 체스판 크기 N
  • N은 10이하의 자연수
• 비숍을 각 칸에 놓을 수 있는지 없는지에 대한 정보다 주어짐
  • 1 : 가능
  • 0 : 불가능

출력

• 체스판위에 놓을 수 있는 비숍의 최대 개수?

접근법

• N퀸이랑 비슷하다는 생각이 들었다
• 비숍을 놓을 때 마다 놓을 수 있는지 없는지 체크하고 넣을 것
  • row, col 값이 같은지 체크(같은 대각선)
• 매 케이스마다 최댓값을 갱신한다.
• 체스판에서 검정칸은 검정칸 끼리만 영향을주고, 흰색칸은 흰색칸끼리만 영향을 준다.
• 검정칸만 도는 경우 따로, 흰색칸만 도는 경우 따로 돌면 시간 복잡도를 줄일 수 있음

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N; // 체스판 크기
    static int[][] map; // 체스판
    static int[][] copyMap; // 체스판 복사본
    static int blackCnt; // 검정칸만 돌았을때 세워놓은 비숍 개수
    static int whiteCnt; // 비숍 개수

    static void onCopyMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                copyMap[i][j] = map[i][j];
            }
        }
    }

    static boolean check(int row, int col) {

        // 현재 위치 기준 좌측상단대각선 탐색하기
        int trow = row, tcol = col;
        while (true) {
            trow--;
            tcol--;

            if (trow < 0 || tcol < 0 || N <= trow || N <= tcol) break;

            if (copyMap[trow][tcol] == 2) return false;
        }

        // 현재 위치 기준 우측상단대각선 탐색하기
        trow = row; tcol = col;
        while (true) {
            trow--;
            tcol++;

            if (trow < 0 || tcol < 0 || N <= trow || N <= tcol) break;

            if (copyMap[trow][tcol] == 2) return false;
        }

        return true;
    }

    static void recur(int row, int col, int total, char color) {
        if (col >= N) {
            row++;
            if (color == 'B') {
                // 검정칸일때 -> (짝수, 짝수) 또는 (홀수,홀수) 좌표만 방문하게 되므로
                if (row % 2 == 0) col = 0;
                else col = 1;
            } else {
                // 흰색칸일때
                if (row % 2 == 1) col = 0;
                else col = 1;
            }
        }

        if (row >= N) {
            if (color == 'B') {
                // 검정 칸일때 최대 비숍 개수
                blackCnt = Math.max(blackCnt, total);
            } else {
                // 흰색 칸일때 최대 비숍 개수
                whiteCnt = Math.max(whiteCnt, total);
            }
            return;
        }

        if (copyMap[row][col] == 1) {
            if (check(row, col)) {
                copyMap[row][col]++;

                recur(row, col + 2, total + 1, color);

                copyMap[row][col]--;
            }
        }

        recur(row, col + 2, total, color);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        copyMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        onCopyMap();
        recur(0, 0, 0, 'B');

        onCopyMap();
        recur(0, 1, 0, 'W');

        bw.write(String.valueOf(blackCnt + whiteCnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 12002. Field Reduction (Silver)

• 링크 : https://www.acmicpc.net/problem/12002

문제 요약

• 소들은 2차원 평면상 서로 다른 위치에 존재
• 울타리는 x축과 y축에 평행한 직사각형 형태
• 최대한 적은 면적의 울타리 안에서 소를 키우려고 함
• 이를 위해 최대 3마리의 소를 팔 예정
• 즉, 세마리 소를 제외한 나머지 소들로 가둘 수 있는 가장 작은 면적의 울타리 계산하기
  • 만약 소가 한줄에 서게 되면 답이 0이 될 수 있음

시간 제한

• 2초

입력

• 소의 수 N
  • 5≤N≤50000
• N개의 줄에 소의 위치를 나타내는 두 정수가 주어짐
  • 1~40000까지의 양의 정수로 표현

출력

• 세 마리 소를 팔았을 때 만들 수 있는 가장 작은 울타리 면적 출력

접근법

N이 5만 개까지 가능하므로,,, 단순히 조합으로 전체 소에서 3개를 고르는 모든 경우를 살피면 안된다.(50000C3 → 시간 초과)

면적은

• 소들의 (x좌표 중 가장 최댓값 - 가장 최솟값) * (y좌표 중 가장 최댓값 - 가장 최솟값)
• 제거할 개수는 3개이고, 면적에 영향을 주는 건 양 끝에 위치한 점들이다.
• 즉 x좌표를 오름차순 했을 때, 앞에서부터 3개 또는 뒤에서부터 3개를 제거한 경우만 보기(y좌표도 마찬가지) ⇒ 총 최대 12 개 좌표 안에서만 보기!
• 제거할 때마다 x 최소/최대, y 최소/최대 갱신할 것

(1,1) (7,8) (10,9) (8,12) (4,100) (50,7)

1. x좌표 기준 좌표 정렬 후 → 앞에서 3개, 뒤에서 3개 가져온다
   이미 가져온 친구는 X
2. y좌표 기준 좌표 정렬후 → 앞에서 3개, 뒤에서 3개 가져온다.
   이미 가져온 친구는 X

⇒ 해당 좌표들만 배열이나 리스트에 담고 조합 코드 돌리기

코드

import java.io.*;
import java.util.*;

public class Main {
    // TODO: 배열을 두 개쓰지 않고 풀 수 있는 법 생각하기 + 중복없이 답는 더 좋은 법도,,
    static int[] selected = new int[3]; // 제거할 좌표
    static int N; // 소 마리수
    static int[][] cowsByX; // X좌표 기준 정렬할 소 좌표
    static int[][] cowsByY; // Y좌표 기준 정렬할 소 좌표
    static ArrayList<int[]> list = new ArrayList<>(); // 제거 대상 좌표들 담을 리스트
    static int answer = Integer.MAX_VALUE; // 넓이

    static void recur(int cur, int cnt) {

        if (cur == list.size()) {

            int x, y, minX = cowsByX[0][0], maxX = cowsByX[N - 1][0], minY = cowsByY[0][1], maxY = cowsByY[N - 1][1];
            int cnt1 = 1, cnt2 = 1, cnt3 = 2, cnt4 = 2;
            for (int i = 0; i < 3; i++) {
                x = list.get(selected[i])[0];
                y = list.get(selected[i])[1];

                if (minX == x) minX = cowsByX[cnt1++][0];
                if (maxX == x){ maxX = cowsByX[N - cnt3][0]; cnt3++;}
                if (minY == y) minY = cowsByY[cnt2++][1];
                if (maxY == y){ maxY = cowsByY[N - cnt4][1]; cnt4++;}
            }

            answer = Math.min(answer, (maxX - minX) * (maxY - minY));

            return;
        }

        if (cnt < 3) {
            selected[cnt] = cur;
            recur(cur + 1, cnt + 1);
        }

        recur(cur + 1, cnt);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        cowsByX = new int[N][2];
        cowsByY = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            cowsByX[i][0] = Integer.parseInt(st.nextToken());
            cowsByY[i][0] = cowsByX[i][0];
            cowsByX[i][1] = Integer.parseInt(st.nextToken());
            cowsByY[i][1] = cowsByX[i][1];
        }

        // x좌표 기준 정렬
        Arrays.sort(cowsByX, (o1, o2) -> {
            return o1[0] - o2[0];
        });

        for (int i = 0; i < 3; i++) {

            boolean same1 = false, same2 = false;
            for (int j = 0; j < list.size(); j++) {
                if (list.get(i)[0] == cowsByX[i][0] && list.get(i)[1] == cowsByX[i][1]) same1 = true;
                if (list.get(i)[0] == cowsByX[N - i - 1][0] && list.get(i)[1] == cowsByX[N - i - 1][1]) same2 = true;
            }

            if (!same1) list.add(new int[]{cowsByX[i][0], cowsByX[i][1]});
            if (!same2) list.add(new int[]{cowsByX[N - i - 1][0], cowsByX[N - i - 1][1]});
        }

        // y좌표 기준 정렬
        Arrays.sort(cowsByY, (o1, o2) -> {
            return o1[1] - o2[1];
        });

        for (int i = 0; i < 3; i++) {

            boolean same1 = false, same2 = false;
            for (int j = 0; j < list.size(); j++) {
                if(list.get(i)[0] == cowsByY[i][0] && list.get(i)[1] == cowsByY[i][1]) same1 = true;
                if(list.get(i)[0] == cowsByY[N - i - 1][0] && list.get(i)[1] == cowsByY[N - i - 1][1]) same2 = true;
            }

            if (!same1) list.add(new int[]{cowsByY[i][0], cowsByY[i][1]});
            if (!same2) list.add(new int[]{cowsByY[N - i - 1][0], cowsByY[N - i - 1][1]});
        }

        recur(0, 0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}