[BaekJoon] G4 18430 무기공학

DFS & Backtracking . ..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

'Java' 언어를 활용하여 본 알고리즘 문제를 해결하였습니다.

 

1. 문제

18430번: 무기 공학

 

무기 공학 문제

 

2. 이해

 

부메랑을 만들 나무 재료의 크기는 1 <= N, M <= 5 로, 사이즈가 크지 않기 때문에 완전탐색 방식으로 문제를 해결할 수 있을 것이다.

 

K의 크기는 1 <= K <= 100

 

따라서 5 X 5 사이즈의 나무 재료에서 모든 타일의 K값이 100 이어도 큰 값이 아니므로, int형으로 처리가 가능하다.

 

네 가지 'ㄱ'자 부메랑

 

우선, 네 가지 종류의 부메랑이 있다. 

 

물론 일정 규칙이 있긴 하지만, 편의성을 고려하여 아래 3중 배열로 델타 좌표를 나타냈다.

 

private static final int[][][] boomerang = {
    {{0, 1}, {-1, 0}}, {{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}}
};

총 네 가지 종류의 부메랑이며 각각 중앙 좌표를 기준으로 두 번의 이동이 있고, 각 이동 별로 좌표가 r, c로 두 방식으로 표현된다.

 

따라서 Size는 [4][2][2] 일 것이다.

---

결국 부메랑은 중심을 기준으로 두 방향으로 한 칸씩 뻗은 형태이므로, 중심을 기준으로 탐색을 한다. 

 

그 과정에서 각 depth는 각 부메랑의 중심 위치이다.

 

탐색을 진행할 때, 2차원 좌표를 탐색하므로 2중 for문이 필요하다. 

여기서 한 가지 Skill을 사용하면 아래처럼 편리하고 깔끔한 표현이 가능하다.

 

int nowR = depth / M;
int nowC = depth % M;

 

nowR과 nowC는 좌표의 row, column 값이다.

---

완전 탐색 시, 부메랑의 양 날개 중 하나라도 나무 재료의 범위 밖으로 벗어난다면, 이 경우는 Pass 한다.

 

또한, 이미 부메랑으로 사용한 위치 좌표(부메랑의 중심 + 부메랑의 양 날개)의 나무 재료라면 다음 부메랑의 재료로 사용할 수 없으므로, 이 경우는 역시 Pass 한다.

 

3. 전체 코드

/*
* Memory : 110248KB
* Time: 432ms
* */

package BaekJoon.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G4_18430_무기_공학 {

    private static int N;
    private static int M;
    private static int max = 0;

    private static final int[][][] boomerang = {{{0, 1}, {-1, 0}}, {{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}}};

    private static int[][] treeIngredient;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        treeIngredient = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j=0; j<M; j++)
                treeIngredient[i][j] = Integer.parseInt(st.nextToken());
        }

        makeBoomerang(0, 0);

        System.out.println(max);
    }

    public static void makeBoomerang(int depth, int intensity) {
        if(depth == N * M) {
            max = Math.max(max, intensity);
            return;
        }

        int nowR = depth / M;
        int nowC = depth % M;

        if(!visited[nowR][nowC]) {
            for(int d=0; d<4; d++) {
                Direction d1 = new Direction(nowR + boomerang[d][0][0], nowC + boomerang[d][0][1]);
                Direction d2 = new Direction(nowR + boomerang[d][1][0], nowC + boomerang[d][1][1]);

                if(outOfMapCheck(d1, d2))
                    continue;

                if(visited[d1.r][d1.c] || visited[d2.r][d2.c])
                    continue;

                visited[nowR][nowC] = true;
                visited[d1.r][d1.c] = true;
                visited[d2.r][d2.c] = true;

                int partIntensity = 2 * treeIngredient[nowR][nowC] + treeIngredient[d1.r][d1.c] + treeIngredient[d2.r][d2.c];
                makeBoomerang(depth + 1, intensity + partIntensity);

                visited[nowR][nowC] = false;
                visited[d1.r][d1.c] = false;
                visited[d2.r][d2.c] = false;
            }
        }

        makeBoomerang(depth + 1, intensity);
    }

    public static boolean outOfMapCheck(Direction d1, Direction d2) {
        return d1.r < 0 || d1.c < 0 || d1.r >= N || d1.c >= M || d2.r < 0 || d2.c < 0 || d2.r >= N || d2.c >= M;
    }

    public static class Direction {
        int r;
        int c;

        public Direction(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

4. 생각

2차원 배열을 간단하게 /, % 계산으로 해결해 버리는 것은 처음 알게 되었는데, 꽤 유용한 방식인 것 같다. 이 문제처럼 2차원 좌표를 깊이 완전 탐색 해야 하는 알고리즘 문제가 꽤 있었던 것으로 기억한다.