[백준 / BOJ] 18430 무기 공학 (Java)

문제

출처 : https://www.acmicpc.net/problem/18430

18430번: 무기 공학

N*M그리드가 주어진다.

길동이는 N*M그리드의 각 칸을 적절히 잘라서 부메랑을 만들어야한다.

 

길동이가 만들수있는 부메랑들의 크기의 총합을 가장 크게하는 프로그램을 만드는 문제다.

---

풀이

N과 M이 5가 최대이므로 완전탐색으로 풀수있는 문제였다.

 

백 트래킹으로 구현한 전형적인 백트래킹 문제다. 구현중 주의할점은 아래와 같다.

 

현재 위치를 y,x라 했을때, 다음에 탐색할 범위는  y, x중 하나를 중점으로 잡아야한다.

만약 다음 범위를 y~N, x~M으로 지정할경우, 그 외의 경우는 고려하지못하기때문에 오답이 나온다.

 

주요 소스코드

    private int getBoomerang(int x){
        int ret = 0;
        for(int i = 0; i < N; i++){
            for(int j = x; j < M; j++){
                if(duplicateChecking(i,j)) continue;
                for(int l = 0; l < 4; l++){
                    int wing1 = i+dy[l];
                    int wing2 = j+dx[l];
                    if(duplicateChecking(wing1, j) || duplicateChecking(i, wing2)) continue;
                    flipCheck(i, j, wing1, wing2);
                    ret = Math.max(ret, getBoomerang(j)+calcBoomerangSize(i, j, wing1, wing2));
                    flipCheck(i, j, wing1, wing2);
                }
            }
        }
        return ret;
    }

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/18430%20%EB%AC%B4%EA%B8%B0%20%EA%B3%B5%ED%95%99/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃