📙[Algo] 24.02.27 알고리즘

알고리즘 문제) BOJ 15684. 사다리 조작

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

문제 요약

• N개의 세로선과 M개의 가로선으로 이루어진 사다리가 존재
• 인접한 세로선 사이에 가로선을 놓을 수 있으며, 놓을 수 있는 위치 개수는 H개다
• 두 가로선은 연속하거나 접하면 안 된다.
• 가로선을 추가해서 i번 세로선의 결과가 i번이 나올 수 있도록 사다리게임을 조작해라!

시간 제한

• 2초

입력

• 세로선 개수 N, 가로선 개수 M, 세로선마다 가로선을 놓을 수 있는 위치 개수 H
  • 2 ≤ N ≤ 10
  • 1 ≤ H ≤ 30
  • 0 ≤ M ≤ (N-1)*H
• M개의 줄에 가로선의 정보가 주어진다. (서로 연속되는 경우는 주어지지 않음)
  • a b 로 나타내면 b번 세로선과 b+11번 세로선을 a번 점선 위치에서 연결했다는 의미
    • 1 ≤ a ≤ H
    • 1 ≤ b ≤ N-1
• 가장 위에 있는 점선의 번호는 1번이고 아래로 내려갈 때마다 1 증가(세로선도 가장 왼쪽의 번호가 1이고, 우측으로 갈수록 1 증가)

출력

• i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하기 위해, 추가해야하는 가로선 개수의 최솟값 출력하기
  • 만약 정답이 3보다 큰 값이면 -1 출력
  • 불가능한 경우도 -1 출력

접근법

• 일단 사다리게임을 배열로 어떻게 구현할지 생각!
  N이 5, H 6이라면
     0 1 2 3 4 5 6 7 8 9
  0
  1 1 1 1 0 1 0 1 0 1
  2 1 0 1 0 1 1 1 0 1
  3 1 0 1 1 1 0 1 0 1
  4 1 0 1 0 1 0 1 0 1
  5 1 1 1 0 1 0 1 1 1
  6 1 0 1 0 1 0 1 0 1
  ⇒ int[][] arr = new int[H+1][N*2]; 로 선언하고
  ⇒ 세로선을 지나는 경우 다 1로 표시한다.
  
  • 이때 col은 1 → 3 → 5 로 2씩 증가시키면서 탐색한다.
  • row는 전부 탐색
  ⇒ 이미 놓여진 사다리의 경우 가로선 위치가 x, y로 주어진다면 arr[x][2*y]에 1표시한다.

• 가로선마다 잇는다, 잇지 않는다를 결정한다(즉 arr[i][j]값이 0인 곳에서 결정).
  • 이때 다음과 같은 조건 체크
    • 가로선은 최대 3개까지만 설치할 것
    • 가로선은 연속되면 안 된다.
      • arr[i][j]에 설치하려고 할 때, arr[i][j-2], arr[i][j+2]가 1이면 안됨
• 케이스가 만들어졌다면, i번이 i번으로 떨어지는지 확인하는 메소드 돌리기
  • 사다리는 좌우를 우선으로 탐색해야한다.
    • 만약 좌우값이 0이라면 arr[x+1][y]로 이동.
    • 만약 우측 값이 1이라면 arr[x+1][y+2]로 이동
    • 만약 좌측 값이 1이라면 arr[x+1][y-2]로 이동
• 배열이기 때문에 경계체크도 할 것

코드

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

public class Main {
    static int N, M, H; // N : 세로선 개수, M : 가로선 개수, H : 세로선마다 가로선 놓을 수 있는 위치 개수
    static int[][] map; // 사다리 맵
    static int answer = Integer.MAX_VALUE; // 설치해야할 가로선 최소 개수
    static boolean check; // 연속됐는지 체크하기위한 변수

    // 경계 체크
    static boolean boundaryCheck(int row, int col) {
        return 0 <= row && row <= H && 0 <= col && col < N * 2;
    }

    // 사다리 타기 진행
    static boolean onProgress() {

        int row, tmpCol;
        for (int col = 1; col < 2 * N; col += 2) {
            // 좌우 탐색부터 할 것!
            row = 1;
            tmpCol = col;
            while (row <= H) {
                if (boundaryCheck(row, tmpCol + 1) && map[row][tmpCol + 1] == 1) {
                    // 만약 우측 값이 1이라면(가로선이 있다면)
                    row++;
                    tmpCol += 2;
                } else if (boundaryCheck(row, tmpCol - 1) && map[row][tmpCol - 1] == 1) {
                    // 만약 좌측 값이 1이라면(가로선이 있다면)
                    row++;
                    tmpCol -= 2;
                } else {
                    // 만약 좌우 가로선이 없다면 아래로
                    row++;
                }
            }
            if(col != tmpCol) return  false;
        }

        return true;
    }
    static void recur(int row,int col, int total) {

        // 설치한 가로선 개수가 3개보다 많을 경우는 제외 시켜야함(가지치기 용)
        if (total > 3) return;

        if (col >= N * 2) {
            col = 2;
            row++;
        }

        if (row == H + 1) {

            // i번째에서 출발한게 i번쨰로 도착하는 경우 개수 갱신
            if(onProgress()){ answer = Math.min(answer, total);}

            return;
        }

        check = true;
        // 이미 가로선이 설치된 경우만 빼고 보기
        if (map[row][col] == 0) {

            // 좌 또는 우에 이미 가로선이 설치되면 안 됨 (연속되면 안되니까)
            if ((boundaryCheck(row, col - 2) && map[row][col - 2] == 1)) {
                check = false;
            }
            if ((boundaryCheck(row, col + 2) && map[row][col + 2] == 1)) {
                check = false;
            }

            if (check) {
                // 가로선 설치하기
                map[row][col] = 1;
                recur(row, col + 2, total + 1);

                // 설치한 거 복원
                map[row][col] = 0;
            }
        }

        // 가로선 설치 안 함
        recur(row, col + 2, total);

    }

    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;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        // 세로선에 1표시 -> 사다리 기둥이니까
        map = new int[H + 1][2 * N];
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j < 2 * N; j += 2) {
                map[i][j] = 1;
            }
        }

        // 이미 설치된 가로선 설치
        int row, col;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            col = Integer.parseInt(st.nextToken());
            map[row][col * 2] = 1;
        }

        recur(1, 2, 0);

        bw.write(String.valueOf(answer == Integer.MAX_VALUE ? -1 : answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 17136. 색종이 붙이기

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

문제 요약

• 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

• 색종이를 10*10인 종이에 붙이려고한다.
  • 1*1 크기의 칸으로 나누어져 있으며, 각각의 칸에 0또는 1이 적혀 있다.
  • 1이 적힌 칸은 모두 색종이로 덮여야 한다.
  • 이때 겹치거나, 경계밖으로 나가면 안된다.
  • 0이 적힌 칸은 색종이를 붙이면 안 된다.
• 종이가 주어졌을 때 1이 적힌 칸을 모두 붙이는데 필요한 색종이 최소 개수 구하기

시간 제한

• 1초

입력

• 총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

• 모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다.
• 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

접근법

• 색종이의 종류는 총 5가지이며, 각각 최대 5개씩 존재한다.
• 11, 22, 33, 44, 5*5 ⇒ 정사각형 형태
• 종이의 크기는 10*10으로 고정이며 1인 부분에만 색종이를 붙일 수 있다.
• 색종이를 최소 개수로 하려면 최대한 큰 색종이를 많이 붙일 것…
• (0,0) 순회하면서 1인 경우 색종이를 붙일 것
  • 이때 색종이를 큰것부터 붙일 경우를 생각한다. ⇒ 불가능하면 하나씩 줄이기
    • 붙인다면 방문처리 true를 한다.
  • 붙이는 메소드 ⇒ 현재 row, col ~ row+크기-1, col+크기-1 까지 탐색하면서 0인경우 false를 return 한도록 구현
  • 최종적으로 row의 위치기 10으로 도달했다는 것은 전부 탐색을 했다는 것이므로 이때 색종이 개수를 출력한다. ⇒ 최대한 큰 색종이 부터 붙이는 걸 생각했으므로 처음 나오는게 답이 아닐까?
• 그리디적으로 접근하면 틀림 → 예외 상황 있음
  • 모든 케이스를 보되 더 볼 필요없는 애들은 가지치기 해야함

코드

• visited배열 따로 만든 경우

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

public class Main {
    static int[][] paper = new int[10][10]; // 종이
    static int[] colors = {0, 5, 5, 5, 5, 5}; // 색종이 개수 (인덱스가 변의 길이라 생각)
    static boolean[][] visited = new boolean[10][10]; // 방문 체크
    static int answer = Integer.MAX_VALUE; // 붙여야하는 색종이 최소 개수

    // 색종이를 붙일 수 있는지 체크한다.
    static boolean isAble(int row, int col, int s) {
        // row : 행 위치, col : 열 위치, s: 변 길이

        // 색종이를 붙였을 때 경계를 벗어날 경우 붙일 수 없으므로
        if (10 < row + s || 10 < col + s) {
            return false;
        }

        for (int i = row; i < row + s; i++) {
            for (int j = col; j < col + s; j++) {
                if (paper[i][j] == 0 || visited[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }

    static void recur(int row, int col, int count) {
        // count : 필요한 색종이 개수

        // 이걸 추가해야 시간초과 안뜬다. => count가 answer보다 커지는 경우는 더 볼 필요도 없음
        if(count > answer) return;

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

        if (row == 10) {
            answer = Math.min(answer, count);
            return;
        }

        if (paper[row][col] == 1 && **!visited[row][col]**) {
            for (int i = 5; i >= 1; i--) {
                // 색종이 종류만큼 체크
                if (0 < colors[i] && isAble(row, col, i)) {
                    // 색종이를 붙였다면 색종이 개수 카운트
                    colors[i]--;

                    // 색종이를 붙일 수 있다면 방문체크
                    for (int j = row; j < row + i; j++) {
                        for (int k = col; k < col + i; k++) {
                            visited[j][k] = true;
                        }
                    }

                    recur(row, col + i, count + 1);

                    // 색종이 개수 복원
                    colors[i]++;

                    // 방문 체크 해제 해주기
                    for (int j = row; j < row + i; j++) {
                        for (int k = col; k < col + i; k++) {
                            visited[j][k] = false;
                        }
                    }
                }
            }
        } else {
            recur(row, col + 1, count);
        }
    }

    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 < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recur(0, 0, 0);

        if (answer == Integer.MAX_VALUE) {
            bw.write(String.valueOf(-1));
        } else {
            bw.write(String.valueOf(answer));
        }

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

• visited 배열 안 만들고 배열 원소값을 1→0으로 바꾸는 방식을 쓸 경우

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

public class Main {
    static int[][] paper = new int[10][10]; // 종이
    static int[] colors = {0, 5, 5, 5, 5, 5}; // 색종이 개수 (인덱스가 변의 길이라 생각)
    static int answer = Integer.MAX_VALUE; // 붙여야하는 색종이 최소 개수

    // 색종이를 붙일 수 있는지 체크한다.
    static boolean isAble(int row, int col, int s) {
        // row : 행 위치, col : 열 위치, s: 변 길이

        for (int i = row; i < row + s; i++) {
            for (int j = col; j < col + s; j++) {
                if (!boundaryCheck(i, j) || paper[i][j] == 0) {
                    // 이미 방문한 곳인지도 체크해야함 ㅠㅠ
                    return false;
                }
            }
        }

        return true;
    }

    // 색종이를 붙였을 때 경계를 벗어날 경우 붙일 수 없으므로
    static boolean boundaryCheck(int row, int col) {

        if (row < 0 || col < 0 || 10 <= row || 10 <= col) {
            return false;
        }

        return true;
    }

    static void recur(int row, int col, int count) {
        // count : 필요한 색종이 개수

        // 이걸 추가해야 시간초과 안뜬다. => count가 answer보다 커지는 경우는 더 볼 필요도 없음
        if(count >= answer) return;

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

        if (row == 10) {
            answer = Math.min(answer, count);
            return;
        }

        if (paper[row][col] == 1) {
            for (int i = 5; i >= 1; i--) {
                // 색종이 종류만큼 체크
                if (0 < colors[i] && isAble(row, col, i)) {
                    // 색종이를 붙였다면 색종이 개수 카운트
                    colors[i]--;

                    // 색종이를 붙일 수 있다면 방문체크
                    for (int j = row; j < row + i; j++) {
                        for (int k = col; k < col + i; k++) {
                            paper[j][k] = 0;
                        }
                    }

                    recur(row, col + i, count + 1);

                    // 색종이 개수 복원
                    colors[i]++;

                    // 방문 체크 해제 해주기
                    for (int j = row; j < row + i; j++) {
                        for (int k = col; k < col + i; k++) {
                            paper[j][k] = 1;
                        }
                    }
                }
            }
        } else {
            recur(row, col + 1, count);
        }
    }

    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 < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recur(0, 0, 0);

        if (answer == Integer.MAX_VALUE) {
            bw.write(String.valueOf(-1));
        } else {
            bw.write(String.valueOf(answer));
        }

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