[BaekJoon] 백준 17136번 _ 색종이 붙이기 for JAVA

 

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

 

문제

 

 

---

 

생각보다 되게 어려움;;;;

 

 

왜냐? 무한루프 엄청 돌았다.ㅋㅋㅋㅋ

 

 

10x10이고 색종이도 1x1, 2x2, 3x3, 4x4, 5x5밖에 없어서 완탐이구나 했음

 

 

조금 생각해보면 무작정 큰걸 붙인다고 최선인건 아니라는걸 알 수 있다.

 

그래서 만약에 맵에서 1을 만났을 때 1x1, 2x2, 3x3, 4x4, 5x5 중에 하나를 붙일 테니까

 

 

각자 붙일 수 있는지 확인하고 붙이는 방식으로 백트래킹을 구현하기로 하였다.

 

 

주의할 점은 1x1, 2x2, 3x3, 4x4, 5x5을 모두 붙일 수 없는 경우를 고려해야한다는 점...! 붙일 수 있는게 없다면 그냥 리턴으로 그 길은 포기해야한다.

 

 

이거 안해줬다가 전부 1인 테케에서 무한로프 돌음요ㅎㅎ

 

 

+ 재귀 안에서 for문 돌 때 x,y값에서 x값은 파라미터로 넘겨줘도 되는데 y값은 넘기면 안됨

 

왜냐면 넘긴 j값이 안쪽에 있는 두번째 for문을 돌지 못하면 밖에 있는 x를 탐색하는 for문도 돌 수 없어서

 

그 2중 for문 자체가 돌지를 않는다.

 

 

 

 

코드를 보며 이해하잣

 

코드

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

public class Main {
	
	static int[][] map;
	static int paper = 0;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		map = new int[10][10];
		
		for(int i=0; i<10; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<10; j++) {
				int in = Integer.parseInt(st.nextToken());
				if(in == 1) paper += 1;
				map[i][j] = in;
			}
		}
		
		dfs(0,0,0,0,0,0,0);
		if(answer ==  Integer.MAX_VALUE) answer = -1;
		System.out.println(answer);
	}
	static int answer = Integer.MAX_VALUE;
	private static void dfs(int one, int two, int three, int four, int five, int p, int x) {
		if(one > 5 || two > 5 || three > 5 || four > 5 || five > 5) {
			return;
		}
		if(one+two+three+four+five > answer) {
			return;
		}
		if(p == paper) {
			answer = Math.min(answer, one+two+three+four+five);
			return;
		}
		
		for(int i=x; i<10; i++) {
			for(int j=0; j<10; j++) {
				// 1. 1이고 방문하지 않았다면 
				
				// 1-1. 1x1이 되는지 확인
				if(map[i][j] == 1) {
				map[i][j] = 0;
					dfs(one+1, two, three, four, five, p+1, i);
					map[i][j] = 1;
				}
				// 1-2. 2x2가 되는지 확인
				if(map[i][j] == 1 && conf(i, j, 2)) {
					// 이미 방문처리는 했으므로 dfs 돌리고 다시 백트래킹
					
					dfs(one, two+1, three, four, five, p+4, i);
					back(i,j,2);
				}
				// 1-3. 3x3 되는지 확인 
				if(map[i][j] == 1 && conf(i, j, 3)) {
					// 이미 방문처리는 했으므로 dfs 돌리고 다시 백트래킹
					
					dfs(one, two, three+1, four, five, p+9, i);
					back(i,j,3);
				}
				// 1-4. 4x4 되는지 확인 
				if(map[i][j] == 1 && conf(i, j, 4)) {
					// 이미 방문처리는 했으므로 dfs 돌리고 다시 백트래킹
					
					dfs(one, two, three, four+1, five, p+16, i);
					back(i,j,4);
				}
				// 1-5. 5x5 되는지 확인 
				if(map[i][j] == 1 && conf( i, j, 5)) {
					// 이미 방문처리는 했으므로 dfs 돌리고 다시 백트래킹
					
					dfs(one, two, three, four, five+1, p+25, i);
					back(i,j,5);
					
				}
				if(map[i][j] == 1) return;
			}
		}
	}
	private static boolean conf(int x, int y, int n) {
		for(int i=x; i<x+n; i++) {
			for(int j=y; j<y+n; j++) {
				if(i >= 10 || j >= 10) return false;
				// 방문한 곳이라면 끝
				if(map[i][j] == 0) {
					return false;
				}
			}
		}
		// 내려왔으면 방문할 수 있는곳임 
		// visited 처리한다.
		for(int i=x; i<x+n; i++) {
			for(int j=y; j<y+n; j++) {
				if(i >= 10 || j >= 10) return false;
				map[i][j] = 0;
			}
		}
		
		return true;
	}
	private static void back(int x, int y, int n) {
		for(int i=x; i<x+n; i++) {
			for(int j=y; j<y+n; j++) {
				map[i][j] = 1;
			}
		}
	}

}

 

 

성능: 위에가 저 코드, 아래는 clone맵 쓴 코드

 

 

1개 개수, 2개 개수 어쩌구는 배열로 해도 되는데 그냥 저때 배열쓰기 싫어서 변수 5개 썼다 ㅎ.ㅎ

 

처음에는 visited를 방문처리하기 위해 clone맵을 하나 만들어서 복제하고

 

그곳에서 방문처리를 하다가 밑으로 내려오면 (=방문할 수 있는 곳이면) clone맵을 다시 map으로 복사하는 작업을 거쳤는데

 

 

맞긴 했지만 성능이 많이 구렸다.

 

생각해보면 복제하려고 맵 100번을 2번 도는것보다 n^2 도는게 낫긴 하다. 헤헤