구현 ( 백트래킹 )
백준 15686번 구현 문제를 백트래킹을 이용해 Java로 풀어보았다.
백트래킹 기법은 그동안 개념 자체는 봤었는데 실제로 이용해보기는 처음이었다. DFS와 어떻게 다른지도 처음으로 알아보게 됐다.
사실 이 문제는 백트래킹 기법에 대해서도 몰랐고, 이 개념과 상관없이도 문제 해결 방법 자체를 전혀 근접하게도 생각해내지 못했기 때문에 후에 다시 스스로 도움 없이 풀어봐야겠다.
문제 아래와 같다. 
굳이 다 확인할 필요가 없다면
이차원 배열로 주어지는 map 형태에 익숙해진 나머지 디폴트로 이중 for문을 이용해 다 탐색해대는 짓이 습관이 돼버렸다.
오늘 이 문제는 우리의 관심사만을 탐색해줘야 한다. 그러지 않으면 시간 초과가 난다.
결국 우리의 관심사는 가정집과 치킨집 둘 사이의 관계다. 빈 칸을 굳이 탐색할 필요가 없다는 것이다. 따라서 가정집과 치킨집을 입력 받을 때마다 따로 그들의 좌표를 저장할 자료구조 ArrayList를 이용할 것이다.
이 둘이 담겨있는 ArrayList 두 개를 겹쳐서 이중 for문을 통해 도시의 치킨거리를 갱신해줄 것이다.
백트래킹을 통한 탐색
결국 최대 m개까지의 치킨집만 확인하면 되기 때문에 몇 개의 치킨집을 방문했는지 확인해줄 변수가 필요하다. 또한 어떤 치킨집을 방문했는지 확인하기 위한 인덱스 변수가 필요하다. 이 둘을 parameter로 넘겨주는 backtracking(int idx, int cnt) 메소드를 선언할 것이다.
static void backTracking(int idx, int cnt){
if(cnt==m){
int cityChickenDistance = 0;
for(int i=0; i<house.size(); i++){
int eachChickenDistance = Integer.MAX_VALUE;
for(int j=0; j<chicken.size(); j++){
if(chickenVisited[j]){
int tmpDistance = Math.abs(house.get(i).row - chicken.get(j).row) + Math.abs(house.get(i).col - chicken.get(j).col);
eachChickenDistance = Math.min(eachChickenDistance, tmpDistance);
}
}
cityChickenDistance += eachChickenDistance;
}
minCityChickenDistance = Math.min(minCityChickenDistance, cityChickenDistance);
}
else{
for (int i = idx; i < chicken.size(); i++) {
if (!chickenVisited[i]) {
chickenVisited[i] = true;
backTracking(i + 1, cnt + 1);
chickenVisited[i] = false;
}
}
}처음에는 가정집과 가장 가까운 치킨집 사이의 거리를 구하기 위해 BFS를 사용했는데 위와 같이 관심사를 두 개로 추려서 살펴보면 굳이 BFS를 이용할 필요가 없다.
위의 코드에서 else 부분이 방문한 치킨집과 몇 개의 치킨집을 방문했는지 갱신해줄 부분이기 때문에 저 부분이 백트래킹을 구현한 부분이라고 생각하면 되겠다.
만약 이미 방문한 곳이라면, 즉 방문할 필요가 없는 곳이라면 건너뜀으로써 DFS와 같이 모든 지점을 다 방문하는 특성과 차이점을 확인할 수 있다.
아래는 내가 제출한 코드다. 물론 나중에 다시 자력으로 다시 풀어봐야겠다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class boj15686 {
static int n,m, minCityChickenDistance = Integer.MAX_VALUE;
static int[][] map;
static ArrayList<Pos> house = new ArrayList<>(), chicken = new ArrayList<>();
static boolean[] chickenVisited;
public static void main(String args[]) throws IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(bfr.readLine());
n = Integer.parseInt(stk.nextToken()); m = Integer.parseInt(stk.nextToken());
map = new int[n+1][n+1];
for(int i=1; i<=n; i++){
stk = new StringTokenizer(bfr.readLine());
for(int j=1; j<=n; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
if(map[i][j]==2) { // 치킨집 좌표 추가
chicken.add(new Pos(i,j));
}
else if(map[i][j]==1){ // 가정집 좌표 추가
house.add(new Pos(i,j));
}
}
}
chickenVisited = new boolean[chicken.size()];
backTracking(0,0);
bfw.write(String.valueOf(minCityChickenDistance));
bfw.close();
}
static void backTracking(int idx, int cnt){
if(cnt==m){
int cityChickenDistance = 0;
for(int i=0; i<house.size(); i++){
int eachChickenDistance = Integer.MAX_VALUE;
for(int j=0; j<chicken.size(); j++){
if(chickenVisited[j]){
int tmpDistance = Math.abs(house.get(i).row - chicken.get(j).row) + Math.abs(house.get(i).col - chicken.get(j).col);
eachChickenDistance = Math.min(eachChickenDistance, tmpDistance);
}
}
cityChickenDistance += eachChickenDistance;
}
minCityChickenDistance = Math.min(minCityChickenDistance, cityChickenDistance);
}
else{
for (int i = idx; i < chicken.size(); i++) {
if (!chickenVisited[i]) {
chickenVisited[i] = true;
backTracking(i + 1, cnt + 1);
chickenVisited[i] = false;
}
}
}
}
static class Pos {
int row; int col;
Pos(int row, int col){
this.row = row;
this.col = col;
}
}
}
오늘 배운 것
백트래킹 이란 것을 배웠다. DFS와 같이 재귀를 이용하지만, 모든 지점을 싹 다 도는 것은 아니다. 조건에 부합하지 않으면 건너 뛴다는 점이 다르다.
