📙 Algorithm Solving/Java
📙[Algo] 24.02.27 알고리즘
혜덕hyeduck
2024. 2. 28. 10:33
알고리즘 문제) BOJ 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
- a b 로 나타내면 b번 세로선과 b+11번 세로선을 a번 점선 위치에서 연결했다는 의미
- 가장 위에 있는 점선의 번호는 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는 전부 탐색
- 가로선마다 잇는다, 잇지 않는다를 결정한다(즉 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. 색종이 붙이기
문제 요약
- 색종이의 크기는 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();
}
}