[백준, Java] 25330번, SHOW ME THE DUNGEON, (백트래킹)

 

문제 링크

25330번: SHOW ME THE DUNGEON

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 0 ~ N번까지의 N+1마을이 존재하며, 각 마을에는 1마리의 몬스터가 존재합니다.

2. 각 마을은 0번 마을과 길로 이어져 있습니다.

3. 각 마을의 몬스터는 공격력을 가지고 있으며, 전투 시 지금까지 만난 몬스터의 공격력이 누적되어 체력이 감소하게 됩니다.

4. 각 마을에 몬스터를 처치하면 주민들을 구할 수 있으며, 각 주민의 수는 주어집니다.

5. 체력이 K일 때 최대로 구할 수 있는 주민의 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 백트래킹을 통해서 구할 수 있는 최대 주민 수의 마을 방문 순서를 탐색합니다.

 

3. 탐색을 통해 얻은 최대 주민 수를 결과로 출력합니다.

 

마을 방문 여부(비트마스킹)

 

백트래킹으로 탐색을 진행할 때 각 마을의 방문 여부는 비트 마스킹으로 처리하였습니다.

 

예를 들어, 현재 비트가 1101일 때

 

1, 3, 4번 마을을 방문했다는 것으로 확인할 수 있습니다.

 

각 마을에 대한 방문 확인을 할 때에는 AND(&)을 진행하였습니다.

 

각 마을에 방문 여부 체크는 OR(&)을 진행하였습니다.

 

마을 방문 순서 탐색(백트래킹, 메모이제이션)

 

각 마을을 방문하는 과정을 백트래킹을 통해서 탐색을 진행합니다.

 

또한, 더 이상 탐색하지 않아도 되는 구간인 경우를 확인하기 위해서 메모이제이션을 사용할 예정입니다.

 

 

백트래킹 탐색 중단 조건.

 

1. 메모이제이션한 값보다 현재 체력이 낮은 경우

 

몬스터의 공격으로 감소하는 체력은 마을을 방문하는 순서에 따라 달라집니다.

 

마을 1 몬스터 공격력 : 1

 

마을 2 몬스터 공격력 : 2

 

마을 1 → 마을 2 : 1 + (1 + 2) : 4

 

마을 2 → 마을 1 : 2 + (1 + 2) : 5

 

위와 같이 차이가 생기지만, 구하는 주민의 수는 동일합니다.

 

각 마을 방문한 상황에 체력을 메모이제이션하여, 똑같은 상황일 때 체력이 더 적은 경우 탐색을 더 진행해도 최대 값이 될 수 없기 때문에 탐색을 종료할 수 있습니다.

 

위의 예시로 살펴보면, 

 

체력이 10이고, 마을 1, 2을 방문한 것을 비트마스킹으로 표현하면 11(3)입니다.

 

마을 1 → 마을 2 일 때, DP[3] = 10 - 4 = 6가 저장됩니다.

 

마을 2 → 마을 1 일 때는 DP[3](6) ≥ 5(10 - 5)가 성립됩니다.

 

즉, 마을 2 → 마을 1일 때에는 더 이상 탐색하지 않아도 된다고 볼 수 있는 것입니다.

 

 

2. 누적된 공격력이 주인공의 현재 체력보다 크거나 같을 때

 

모든 몬스터의 공격력은 1이상이기 때문에, 방문하지 않은 어떤 마을을 방문해도 몬스터를 처리할 수 없습니다.

 

즉, 누적된 데미지 ≥ 주인공 현재 체력

 

만족하면, 더 이상 탐색을 진행하지 않습니다.

 

 

 

★ 방문할 마을을 탐색할 때 해당 마을을 방문해서 몬스터를 처리할 수 있는지 확인하는 과정도 항상 있어야 합니다.

 

이 조건들을 이용해서 백트래킹 탐색을 진행하여 최대 주민을 구하는 방문 순서를 진행합니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

 

K : 5

 

마을 정보

 

	마을1	마을2	마을3	마을4	마을5
몬스터 공격력	5	3	1	2	4
주민 수	10	10	10	10	10

 

 

2. 백트래킹을 통해서 구할 수 있는 최대 주민 수의 마을 방문 순서를 탐색합니다.

 

아무 마을도 방문하지 않았음을 표현하는 비트 : 00000

 

백트래킹 진행

 

처음으로 1번 마을 방문

 

체력 : 5 - 5 = 0

 

구한 주민 수 : 10명

 

누적 공격력 : 5

 

방문 비트 : 00001(1)

 

메모이제이션 : DP[1] = 0

 

▶ 이후 마을 탐색에서 누적된 공격력이 현재 주인공 체력보다 크거나 같으므로, 탐색을 종료합니다.

 

 

 

처음으로 2번 마을 방문

 

체력 : 5 - 3 = 2

 

구한 주민 수 : 10명

 

누적 공격력 : 3

 

방문 비트 : 00010(2)

 

메모이제이션 : DP[2] = 2

 

▶ 이후 마을 탐색에서 누적된 공격력이 현재 주인공 체력보다 크거나 같으므로, 탐색을 종료합니다.

 

 

 

처음으로 3번 마을 방문

 

체력 : 5 - 1 = 4

 

구한 주민 수 : 10명

 

누적 공격력 : 1

 

방문 비트 : 00100(4)

 

메모이제이션 : DP[4] = 4

 

다음으로 4번 마을 방문(1, 2, 5번 마을 몬스터 처치 못하므로 방문 불가능)

 

체력 : 4 - (1 + 2) = 1

 

구한 주민 수 : 20명

 

누적 공격력 : 3

 

방문 비트 : 01100(12)

 

메모이제이션 : DP[12] = 1

 

▶ 이후 마을 탐색에서 누적된 공격력이 현재 주인공 체력보다 크거나 같으므로, 탐색을 종료합니다.

 

방문 경로 : 마을 3 → 마을 4

 

 

 

처음으로 4번 마을 방문

 

체력 : 5 - 2 = 3

 

구한 주민 수 : 10명

 

누적 공격력 : 2

 

방문 비트 : 01000(8)

 

메모이제이션 : DP[8] = 3

 

다음으로 방문할 수 있는 마을이 존재하지 않습니다.(1, 2, 5번 마을 몬스터 처치 못하므로 방문 불가능)

 

▶ 3번 마을은 DP[12](1)이기 때문에, 3번 마을을 방문해도 최대값이 되지 못하기 때문에 방문하지 않고 탐색을 종료합니다.

 

 

 

처음으로 5번 마을 방문

 

체력 : 5 - 4 = 1

 

구한 주민 수 : 10명

 

누적 공격력 : 4

 

방문 비트 : 10000(16)

 

메모이제이션 : DP[16] = 1

 

 

▶ 이후 마을 탐색에서 누적된 공격력이 현재 주인공 체력보다 크거나 같으므로, 탐색을 종료합니다.

 

3. 탐색을 통해 얻은 최대 주민 수를 결과로 출력합니다.

 

 

탐색을 통해 얻은 최대 마을 방문 경로 : 마을 3 → 마을 4

 

구한 주민의 수 : 20명

 

 

20 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 마을의 정보를 띄어쓰기 기준 나누었습니다.
• search를 이용하여 최대 주민을 구하는 경로를 탐색합니다.
• 탐색한 최대 주민의 수를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 백트래킹을 통해서 최대 주민을 구하는 경로를 탐색합니다.
• search함수는 메모이제이션을 이용해서 최대값이 될 수 없는 경우 탐색을 중단합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int result = 0;
    static int N, fullVisited;
    static int[] attack, population, DP;
    public static void main(String[] args) throws IOException {
        //입력값 저장하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //attack : 공격력 정보, population : 주민 수 정보
        attack = new int[N];
        population = new int[N];
        fullVisited = (1 << N) - 1;	//모든 마을 방문 시 Bit
        DP = new int[fullVisited+1];	//메모이제이션 진행할 배열
        Arrays.fill(DP, -1);	//메모이제이션 배열 -1으로 초기화
        st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        for(int i=0;i<N;i++){
            attack[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            population[i] = Integer.parseInt(st.nextToken());
        }
        //백트래킹으로 최대 주민 수에 대한 경로 구하기.
        search(K, 0,  0, 0);
        bw.write(String.valueOf(result));	//최대 주민 수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹을 통해서 최대 주민 수에 대한 경로 탐색하는 함수
    static void search(int hp, int save, int damage, int visited){

        //최대 구한 주민 수 비교
        result = Math.max(result, save);

        //모든 마을 방문했거나, 누적된 공격력이 주인공 체력보다 많은 경우
        if(visited == fullVisited || hp <= damage){
            return;
        }

        //다음 방문할 마을 탐색
        for(int i=0;i<N;i++){
            int bit = (1 << i);

            //이미 방문한 마을일 때
            if((visited & bit) > 0){
                continue;
            }

            //해당 마을 방문했을 때 정보들
            int totalDamage = damage + attack[i];
            int nxtHp = hp - totalDamage;
            int nxtVisited = visited | bit;

            //몬스터를 물리치지 못하거나, 메모이제이션으로 최대값이 될 수 없는 경우
            if(nxtHp < 0 || DP[nxtVisited] >= nxtHp){
                continue;
            }
            //다음 마을 방문 진행
            DP[nxtVisited] = nxtHp;
            search(nxtHp, save + population[i], totalDamage, nxtVisited);
        }

    }
}