[백준] 17136.색종이 붙이기 (java) / 백트래킹, DFS

@백트래킹, DFS / 45m (필기 15m 포함)

예전에 두번 풀어봤을 때 두번 다 실패했었는데(설명 듣고도)

오랜만에 풀었는데 한번에 풀어서 뿌듯했다ㅎㅎ

 

 

문제 링크

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

17136번: 색종이 붙이기

 

 

구현 포인트

1. findStart() 로 시작점을 찾는다

이 함수는 1) 어디서부터 시작해야할지 알려주는 기능과 2) 끝났는지 체크하는 기능을 한다.

 

시작점을 찾으면

색종이 크기인 1~5 만큼 돌면서

그릴수 있는지 체크하고

 

무작정 색종이를 붙이면 안되고

if (색종이를 붙일 수 있는지 체크) {

   //붙일 수 있다면

   붙이고();

   그 다음 백트래킹();

   떼주고();

}

이 방식으로 풀었다.

 

 

2. findStart, backTraking 모두 매개변수를 주지 않는다.

원래는 이렇게 매개변수를 줘서 구현했는데

이렇게 구현하고 혹시 몰라서 마지막에 모든 점을 돌았는지 체크하는 함수를 하나 줬었다. (map배열과 visit배열이 일치하는지 체크하는)

 

그런데 이렇게 할 필요 없이 매번 findStart를 (0, 0) 부터 돌게 하면

끝까지 왔다는 것 ((-1, -1)을 리턴했다는 것) 자체가 모든 점을 돌았다는 뜻이 되기 때문에 굳이 이런 체크하는 함수를 쓰지 않아도 된다.

그래서 매개변수가 필요 없어진다.

(원래 DFS, 백트래킹에는 매개변수가 필요하다! 여기서는 findStart 함수가 그 역할을 해 줘서 필요 없는 것)

 

 

 

사실 백트래킹, DFS, BFS, 다익스트라.. 등등은 전부 다 완탐을 기반으로 하기 때문에

findStart에서 시작점을 주는 것은 위험하다.

왜냐면 시작점을 줘서 그 앞에는 안 돌게 하는 것 자체가 완탐의 의미를 벗어나는 것이기 때문에

실제로 시험에서 이렇게 해서 틀리게 나오면, 디버깅 하는데 굉장히 어렵다.

그러니까 백트래킹의 기본 대로 완탐으로 풀도록!

 

 

 

팁 (visit 없이 풀 수 있는 방법)

visit을 사용하지 않고, 그냥 값 * -1을 해주면

1) 붙일 때 * -1

2) 떼낼 때 * -1

하면 원 상태로 돌아온다 (만약 값이 0이라 해도 -1을 곱해봤자 그대로이기 때문에 상관 X)

 

그래서 visit을 사용하지 않고 이 방식으로 풀면 시간이 50ms정도 줄어든다!

 

 

 

visit을 사용한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int minPaper = Integer.MAX_VALUE, paper[];
	private static boolean[][] map, visit;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		paper = new int[] {5, 5, 5, 5, 5};
		map = new boolean[10][10];
		visit = new boolean[10][10];
		
		for (int i = 0; i < 10; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 10; j++)
				if (Integer.parseInt(st.nextToken()) == 1)
					map[i][j] = true;
				else 
					map[i][j] = false;
		}
		
		backTracking();
		
		if (minPaper == Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(minPaper);
	}

	private static void backTracking() {
		Node temp = findStart();
		if (temp.x == -1 && temp.y == -1) {
			countPaper();
			return;
		}

		int nx = temp.x;
		int ny = temp.y;
		
		for (int k = 5; k >= 1; k--) {
			if (paper[k - 1] > 0) {
				paper[k - 1]--;
				if (isPossible(nx, ny, k)) {
					fill(nx, ny, k, true);
					backTracking();
					fill(nx, ny, k, false);
				}
				paper[k - 1]++;
			}
		}
	}

	private static void countPaper() {
		int min = 0;
		for (int i = 0; i < 5; i++)
			min += (5 - paper[i]);
		
		if (minPaper > min) minPaper = min;
	}

	private static void fill(int x, int y, int k, boolean fill) {
		for (int i = 0; i < k; i++)
			for (int j = 0; j < k; j++)
				visit[x + i][y + j] = fill;
	}

	private static boolean isPossible(int x, int y, int k) {
		for (int i = 0; i < k; i++)
			for (int j = 0; j < k; j++)
				if (x + i >= 10 || y + j >= 10 || !map[x + i][y + j] || visit[x + i][y + j])
					return false;
		
		return true;
	}

	private static Node findStart() {
		//무조건 완탐이니까 x, y는 필요 없다!
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++)
				if (map[i][j] && !visit[i][j])
					return new Node(i, j);

		return new Node(-1, -1);
	}
}

 

 

 

visit을 사용하지 않은 코드 (* -1 을 사용해서 푼 코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_novisit {
	private static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int minPaper = Integer.MAX_VALUE, paper[], map[][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		paper = new int[] {5, 5, 5, 5, 5};
		map = new int[10][10];
		
		for (int i = 0; i < 10; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 10; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		backTraking();
		
		if (minPaper == Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(minPaper);
	}

	private static void backTraking() {
		Node temp = findStart();
		if (temp.x == -1 && temp.y == -1) {
			countPaper();
			return;
		}

		int nx = temp.x;
		int ny = temp.y;
		
		for (int k = 5; k >= 1; k--) {
			if (paper[k - 1] > 0) {
				paper[k - 1]--;
				if (isPossible(nx, ny, k)) {
					fill(nx, ny, k);
					backTraking();
					fill(nx, ny, k);
				}
				paper[k - 1]++;
			}
		}
	}

	private static void countPaper() {
		int min = 0;
		for (int i = 0; i < 5; i++)
			min += (5 - paper[i]);
		
		if (minPaper > min) minPaper = min;
	}

	private static void fill(int x, int y, int k) {
		for (int i = 0; i < k; i++)
			for (int j = 0; j < k; j++)
				map[x + i][y + j] *= -1;
	}

	private static boolean isPossible(int x, int y, int k) {
		for (int i = 0; i < k; i++)
			for (int j = 0; j < k; j++)
				if (x + i >= 10 || y + j >= 10 || map[x + i][y + j] != 1)
					return false;
		
		return true;
	}

	private static Node findStart() {
		//무조건 완탐이니까 x, y는 필요 없다!
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++)
				if (map[i][j] == 1)
					return new Node(i, j);

		return new Node(-1, -1);
	}
}

위가 visit을 사용한 코드, 아래가 * -1을 사용한 코드

백트래킹에 대해 다시 한번 공부해 볼 수 있는 문제였다.

 

끝!