[JAVA] 백준 12869. 뮤탈리스크(DFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 DFS를 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제 페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

 문제가 일단 굉장히 흥미로웠습니다. 대한민국 민속놀이인 만큼 문제 이름을 보고 대부분의 사람들은 흠칫하셨을 것 같아요.

 풀이방법은 3기의 SCV의 HP를 각각 hp1, hp2, hp3라고 할 때, 각 hp에 대해 -9, -3, -1의 작업을 재귀호출로 시도해보기로 했습니다. 1차 풀이 결과는 '시간초과'

 

 아마 이유는 쓸데 없는 작업이 많아서 그럴거라고 생각했습니다. 그래서 각 작업의 count값을 저장하니까 그 count 값보다 커지면 바로 return을 해서 더 깊이 들어가지 않게 만들었습니다. 2차 풀이 결과도 '시간초과'

 

 방법 자체에 문제는 없어 보였는데 계속 시간초과가 나서 고민하고 지인과 의견도 나누어 본 결과, 수행하는 작업을 더 줄일 수 있었습니다. 바로 케이스 중복을 제거함으로서 말이죠.

 예를 들어 hp1=10, hp2=7, hp3=9 일 때와 hp1=9, hp2=10, hp3=7 일 때의 작업은 같은 작업입니다. {-9, -3, -1}, {-9, -1, -3}, {-3, -9, -1}, {-3, -1, -9}, {-1, -3, -9}, {-1, -9, -3} 의 6가지 작업 수가 있는데 3기의 hp 조합이 같다면 결국 같은 작업이 되어버리는거죠. 그래서 들어오는 hp 3개의 값을 정렬한 뒤 방문처리를 위한 3차원 배열을 두어 처리했더니 통과했습니다.

 

4. 로직

1. {-9,-3,-1} {-9,-1,-3} {-1,-3,-9} {-1,-9,-3} {-3,-9,-1} {-3,-1,-9} 의 6작업을 매개변수로 넘기면서 재귀호출로 실행한다.

2. 계산 후 들어온 hp1, hp2, hp3를 정렬한다.

3. 각 hp가 음수인 경우 0으로 바꾸고, 모든 hp가 0이면 최소 카운트인지 확인하고 재설정 [종료]

4. arr[hp1][hp2][hp3] = 1이라면(방문) 이미 처리한 hp조합이므로 return [종료]

5. arr[hp1][hp2][hp3] = 0이라면(미방문) 1로 바꾼다.

6. 1의 작업 수행

 

5. 코드

package kr.youngsu.baekjoon.sw12869_Mutalisk_;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static ArrayList<Integer> scvHP;
    static int[][][] visited;
    static int[] damage = new int[] {9, 3, 1};
    static int minCnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        N = Integer.parseInt(st.nextToken());
        scvHP = new ArrayList<>();
        visited = new int[61][61][61]; 
        minCnt = Integer.MAX_VALUE;
        
        st = new StringTokenizer(br.readLine().trim());
        for(int i = 0; i < N; i++) {
            scvHP.add(Integer.parseInt(st.nextToken()));
        }
        for(int i = N; i < 3; i++) {
            scvHP.add(0);
        }
        
        solveDFS(scvHP.get(0), scvHP.get(1), scvHP.get(2), 0);
        
        System.out.println(minCnt);
        return;
    }
 
    private static void solveDFS(int hp1, int hp2, int hp3, int cnt) {
        hp1 = Math.max(0, hp1);
        hp2 = Math.max(0, hp2);
        hp3 = Math.max(0, hp3);
        int max = Math.max(Math.max(hp1, hp2), hp3);
        int min = Math.min(Math.min(hp1, hp2), hp3);
        int mid = hp1 + hp2 + hp3 - max - min;
        hp1 = max;
        hp2 = mid;
        hp3 = min;
        
        if(hp1 <= 0 && hp2 <= 0 && hp3 <= 0) {
            minCnt = Math.min(cnt, minCnt);
            return;
        }
        
        if(visited[hp1][hp2][hp3] == 1) {
            return;
        } else {            
            visited[hp1][hp2][hp3] = 1;
        }
        
        // 불필요한 작업 제거
        if(minCnt < cnt) {
            return;
        }
        
        solveDFS(hp1-9, hp2-3, hp3-1, cnt+1);
        solveDFS(hp1-9, hp2-1, hp3-3, cnt+1);
        solveDFS(hp1-3, hp2-9, hp3-1, cnt+1);
        solveDFS(hp1-3, hp2-1, hp3-9, cnt+1);
        solveDFS(hp1-1, hp2-3, hp3-9, cnt+1);
        solveDFS(hp1-1, hp2-9, hp3-3, cnt+1);
        
        return;
    }
}
 

 

6. 결과