🔗문제 링크
🔒 문제 설명
위 그림과 같이 5종류의 색종이가 각 종류별로 5장씩 있다.
색종이를 10x10 크기의 종이에 붙이려고한다.
종이의 각 칸에는 0과 1중 하나의 숫자가 적혀있으며, 1이 적힌 칸을 색종이로 모두 덮으려고 한다.
색종이를 붙일 때는 종이의 경계밖으로 나가서는 안되고, 겹쳐도 안된다. 또한 0이 적힌칸에는 색종이가 있으면 안된다.
1이 적힌 모든 칸에 색종이를 붙이는데 필요한 색종이의 최소 갯수를 구하자.
🧾 입력 예시
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
🔎 출력 예시
7
🔑 문제 풀이
🔧 처음 시도한 풀이
for(int x = 5 ; x>0 ; x--) { // x : 색종이 크기 boolean nextSize = false; for(int i=0 ; i<=10-x ; i++) { for(int j=0 ; j<=10-x ; j++) { if(map[i][j]==1 && !visited[i][j]) { if(chkOne_and_True(i,j,x)) { // 모두 1이고 모두 방문한 적 없는 칸 if(paper[x]>0) { paper[x]--; visit(i,j,x); } if(paper[x]==0) { nextSize = true; break; } } } } if(nextSize) break; } } for(int i=1 ; i<=5 ; i++) { ret += (5-paper[i]); } if(allPass()) { System.out.println(ret); }else { System.out.println(-1); }큰 색종이 부터 채워넣으면 될 것 같아서 크기가 5인 색종이부터 완전 탐색을 한 후 사이즈를 줄이고 위 과정을 반복하였으나 결과적으로 오답이었다.
아래와 같은 반례를 찾을 수 있었다.
🔑 풀이
-
입력값을 받는 map과 방문기록을 담는 visited 생성
-
map 중 1인 좌표를 list에 담는다.
-
list의 값을 순회하면서 해당 좌표가 방문기록이 없다(false)면
-
크기가 5부터 1까지 dfs를 타고 들어감
-
allpass()를 통하여 1인 부분을 모두 방문했다면 ret값을 갱신해준다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
Main z = new Main();
z.solution();
}
int[][] map;
int ret = 0;
List<int[]> list;
private void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ret = Integer.MAX_VALUE;
int[] paper = new int[6];
list = new ArrayList<>();
Arrays.fill(paper, 5);
boolean[][] visited = new boolean[10][10];
map = new int[10][10];
for(int i=0 ; i<10 ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0 ; j<10 ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==1) {
list.add(new int[] {i,j});
}
}
}
dfs(0, visited, paper, 0);
if(ret<Integer.MAX_VALUE) {
System.out.println(ret);
}else {
System.out.println(-1);
}
}
private void dfs(int dep,boolean[][] visited,int[] paper, int curIdx) {
if(allPass(visited)) {
ret = Math.min(ret, dep);
return;
}
if(curIdx>=list.size()) {
return;
}
int row = list.get(curIdx)[0];
int col = list.get(curIdx)[1];
int[] pos = {row,col};
if(map[row][col]==1 && !visited[row][col]) {
for(int x = 5 ; x>0 ; x--) {
if(Arrays.equals(pos, new int[] {-1,-1})) {
break;
}
if(chkOne_and_True(visited, pos, x)) {
if(countPaper(paper, x)) {
// 종이 사용 가능
visit(visited, pos, x, true);
dfs(dep+1,visited,paper,curIdx+1);
paper[x]++;
visit(visited, pos, x, false);
}else {
continue;
}
}
}
}else {
dfs(dep, visited, paper, curIdx+1);
}
}
private boolean allPass(boolean[][] visited) {
for(int i=0 ; i<10 ; i++) {
for(int j=0 ; j<10 ; j++) {
if(map[i][j]==1) {
if(!visited[i][j]) {
return false;
}
}
}
}
return true;
}
private void visit(boolean[][] visited, int[] pos, int len,boolean b) {
int row = pos[0];
int col = pos[1];
for(int i=row ; i<row+len ; i++) {
for(int j=col ; j<col+len ; j++) {
visited[i][j] = b;
}
}
}
private int[] nextPos(int[] befo) {
int[] nPos = new int[2];
int row = befo[0];
int col = befo[1];
if(col<9) {
nPos[0] = row;
nPos[1] = col+1;
}else if(row<9){
nPos[0] = row+1;
nPos[1] = 0;
}else {
nPos[0] = -1;
nPos[1] = -1;
}
return nPos;
}
private boolean chkOne_and_True(boolean[][] visited, int[] pos, int len) {
if(!inRange(pos,len)) {
return false;
}
int row = pos[0];
int col = pos[1];
for(int i=row ; i<row+len ; i++) {
for(int j=col ; j<col+len ; j++) {
if(map[i][j]==1 && !visited[i][j]) {
continue;
}else {
return false;
}
}
}
return true;
}
private boolean countPaper(int[] paper, int len) {
if(paper[len]>0) {
paper[len]--;
return true;
}
return false;
}
private boolean inRange(int[] pos, int len) {
int row = pos[0];
int col = pos[1];
if(row+len<=10 && col+len<=10)
return true;
return false;
}
}📇 결과
