백준 15686번( 자바 )

Flash·2022년 1월 16일
0

BOJ-Algorithm

목록 보기
29/51
post-thumbnail

구현 ( 백트래킹 )

백준 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와 같이 재귀를 이용하지만, 모든 지점을 싹 다 도는 것은 아니다. 조건에 부합하지 않으면 건너 뛴다는 점이 다르다.

profile
개발 빼고 다 하는 개발자

0개의 댓글