[백준] 17136번 색종이 붙이기 (자바 풀이)
- 알고리즘 문제 해결(PS)/[백준]
- 2022. 3. 3.
문제
https://www.acmicpc.net/problem/17136
풀이
이 문제는 DFS와 백트래킹을 사용하여 해결할 수 있다. DFS를 통해 모든 원소를 탐색하면서 색종이를 붙일 수 있는지 체크한다. 이때 색종이의 개수를 저장하는 배열을 하나 만들고, 색종이를 붙일 수 있다면 색종이를 붙인다. 이후 다시 dfs 탐색을 진행하는 식으로 해결하면 된다.
코드
import java.io.*;
import java.util.*;
public class Baekjoon_17136 {
static int map[][] = new int[10][10];
static int paper[] = {0,5,5,5,5,5};
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i=0; i<10; i++) {
for(int j=0; j<10; j++) {
map[i][j] = sc.nextInt();
}
}
dfs(0,0,0);
if(ans==Integer.MAX_VALUE) {
System.out.println(-1);
}else{
System.out.println(ans);
}
}
public static void dfs(int x, int y, int cnt) {
if(x >= 9 && y >9) {
ans = Math.min(ans, cnt);
return;
}
if(ans <= cnt) { // ans보다 cnt가 크면 탐색할 필요 없음
return;
}
if(y>9) { // 가로줄 전부 봄. 아래 줄로 이동
dfs(x+1,0,cnt);
return;
}
if(map[x][y] ==1) {
for(int i=5; i>=1; i--) {
if(paper[i] >0 && check(x,y,i)) { // 색종이가 남아있고, 붙일 수 있다면
change(x,y,i,0); // 색종이 붙임
paper[i]--;
dfs(x,y+1,cnt+1);
change(x,y,i,1); // 색종이 뗌
paper[i]++;
}
}
}else { // 오른쪽으로 이동
dfs(x,y+1, cnt);
}
}
/* 상태를 바꾸는 함수. 0->1, 1->0 */
public static void change(int x, int y, int size, int state) {
for(int i=x; i<x+size; i++) {
for(int j=y; j <y+size; j++) {
map[i][j] = state;
}
}
}
/* 색종이를 붙일수 있는지 체크하는 함수 */
public static boolean check(int x, int y, int size) {
for(int i=x; i<x +size; i++) {
for(int j=y; j< y+size; j++) {
if(i<0 || i>=10 || j<0 || j >=10) { // 범위 벗어남
return false;
}
if(map[i][j] != 1) { // 1이 아님
return false;
}
}
}
return true;
}
}
결과
반응형
'알고리즘 문제 해결(PS) > [백준]' 카테고리의 다른 글
[백준] 2146번 다리 만들기 (자바 풀이) (0) | 2022.03.04 |
---|---|
[백준] 1790번 수 이어 쓰기 2 (자바 풀이) (0) | 2022.03.04 |
[백준] 11286번 절댓값 힙 (자바 풀이) (0) | 2022.03.02 |
[백준] 14431 소수마을 (자바 풀이) (0) | 2022.02.25 |
[백준] 1644번 소수의 연속합 (자바 풀이) (0) | 2022.02.23 |