그래도 해야지.
백준 17136번 색종이 붙이기를 바탕으로 백트래킹을 이해해보자.
1. DFS - 백트래킹
코딩테스트에서 백트래킹을 활용하여 풀어야하는 문제는 종종 나온다.
개인적으로 BFS, DFS는 개념적인 어려움보단 구현에 있어 신경써야하는 것들이 좀 있고,
풀기위해서 세팅해야하는 것들이 많아 구현만 어느정도 익숙해지면 놓치기 아까운 문제라고 생각한다.
DFS를 활용한 백트래킹을 어떻게 구현하는 지 단계별로 정리해보자.
import java.io.*;
import java.util.StringTokenizer;
// 각 종류 색종이 5개씩
public class Main {
private static int[][] adj = new int[10][10];
private static int[] paper = {0, 5, 5, 5, 5, 5};
private static int answer = Integer.MAX_VALUE;
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++) {
adj[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0);
if (answer == Integer.MAX_VALUE) {
bw.write("-1");
} else {
bw.write(Integer.toString(answer));
}
bw.flush();
br.close();
bw.close();
}
private static void dfs(int yx, int count) {
if (count >= answer) return;
if (yx == 100) {
if (answer > count) {
answer = count;
}
return;
}
int y = yx / 10;
int x = yx % 10;
if (adj[y][x] == 1) {
for (int i = 1; i <= 5; i++) {
if (paper[i] > 0 && check(y, x, i)) {
fill(y, x, i, 0);
paper[i]--;
dfs(yx + 1, count + 1);
fill(y, x, i, 1);
paper[i]++;
}
}
} else {
dfs(yx + 1, count);
}
}
private static boolean check(int y, int x, int size) {
if ((y + size) > 10 || (x + size) > 10) return false;
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if (adj[i][j] == 0) return false;
}
}
return true;
}
private static void fill(int y, int x, int size, int flag) {
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
adj[i][j] = flag;
}
}
}
}그래프 및 공유할 변수들
private static int[][] adj = new int[10][10];
private static int[] paper = {0, 5, 5, 5, 5, 5};
private static int answer = Integer.MAX_VALUE;전역으로 설정하자. 정신건강을 위해서.
메서드 파라미터로 넘길 수 있는데, 머리아프다.
문제 푸는데 의의를 두고 전역으로 두자.
파이썬은 global 변수로 관리해야하는데, 자바는 클래스 내에서 전역으로 설정하면 클래스 내에서 공유가 되니 이건 파이썬보다 훨씬 편하다.
탐색 위치 체크 및 방문 여부 체크 그리고 액션
private static boolean check(int y, int x, int size) {
if ((y + size) > 10 || (x + size) > 10) return false;
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if (adj[i][j] == 0) return false;
}
}
return true;
}그래프를 인접행렬로 구현했다면 필수적으로 해야하는 부분이다.
만약, 그래프를 인접리스트로 구현했다면 방문여부만 체크해주면 된다.
if (adj[i][j] == 0) return false;이 문제에서는 방문여부를 색종이로 채웠냐 안채웠냐로 체크를 한다.
다른 문제에서는 방문여부를 별도의 boolean 배열을 전역으로 설정해서 체크해주는 경우가 많다.
private static void fill(int y, int x, int size, int flag) {
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
adj[i][j] = flag;
}
}
}방문을 했을 경우 취할 액션이다.
색종이 붙이기 문제에서는 그래프에 종이를 덮는다 가 액션이다.
해당 문제에서는 방문여부를 true로 변환해주는 액션을 이렇게 변형을 한 것이다.
백트래킹 구현
private static void dfs(int yx, int count) {
if (count >= answer) return;
if (yx == 100) {
if (answer > count) {
answer = count;
}
return;
}
int y = yx / 10;
int x = yx % 10;
if (adj[y][x] == 1) {
for (int i = 1; i <= 5; i++) {
if (paper[i] > 0 && check(y, x, i)) {
fill(y, x, i, 0);
paper[i]--;
dfs(yx + 1, count + 1);
fill(y, x, i, 1);
paper[i]++;
}
}
} else {
dfs(yx + 1, count);
}
}단순히 짧은 경로를 탐색할 때는 재귀에서 빠져나오는 경우, 복원해주야하는 요소가 없다.
목표지점까지 경로를 카운팅해주고, 최소값을 답으로 던져주면 되니깐.
그런데 백트래킹은 다르다.
재귀에서 빠져나올때 방문여부나 변화된 변수들 상태들을 복원해주어야한다.
다른 방법으로 같은 경로를 접근할 때, 이전에 했던 방법이 영향을 주면 안되니깐.
fill(y, x, i, 0);
paper[i]--;
dfs(yx + 1, count + 1);
fill(y, x, i, 1);
paper[i]++;색종이 붙이기 문제애서는 방문시 액션이 종이를 채우는 것이다. 그리고 가지고 있는 종이 갯수를 소모하는 것.
재귀에서 빠져나올 때 이 액션을 복원해주는 것이다.
다른 액션을 취할 때 영향을 주면 안되니깐.
if (count >= answer) return;
if (yx == 100) {
if (answer > count) {
answer = count;
}
return;
}조건을 만족하는 경우 재귀를 마무리하는 것을 상단에 구현한다.
재귀에 들어왔을 때, 현재 위치가 최종 종착지인지 여부를 체크해준다.
그리고 최소값을 구하는 건데, 이미 현재 카운팅하고 있는 값이 최소값보다 크다면 그 경로는 더이상 탐색을 하지 않아도 되니, 가지치기를 해준다! (최적화)
DFS - 백트래킹 구조
1. 그래프 및 공유할 변수들 설정
2. 탐색 위치 체크 및 방문 여부 체크 그리고 액션
3. 백트래킹 구현: 복원과 가지치기
2. 정리하며...
DFS, BFS 기본 문제를 많이 풀어서 자신있다고 생각했는데, 색종이 붙이기 문제는 신경써야할 것들이 많이 변형되어서 많이 당황스러웠다.
방문시 취해야할 액션들을 하나하나 정리해서 그대로 구현에만 옮긴다면 큰 문제는 없을 것으로 생각된다.
계속 나아가자, 될 때까지.
