18430 - 무기공학 (Java)

🔗 문제 링크: 백준 18430번 - 무기 공학

---

📌 문제 설명

• N × M 크기의 격자에서 부메랑 모양의 무기를 배치하여 최대한 강한 무기를 제작하는 문제.
• 부메랑은 네 가지 형태로 배치 가능하며, 2 × 중심값 + 나머지 두 값으로 점수를 계산.
• 서로 겹치지 않게 배치해야 하며, 최대 점수를 출력하는 것이 목표.

---

💡 풀이 방법: 백트래킹(DFS) 탐색

🚀 백트래킹을 사용하여 모든 가능한 부메랑 배치를 탐색하고, 최댓값을 갱신하는 방식으로 해결.

🔹 1️⃣ 완전 탐색 (Brute Force) 시도

• N × M에서 부메랑을 배치하는 모든 경우를 탐색.
• O(4^(N×M))로 경우의 수가 기하급수적으로 증가 → 비효율적!

🔹 2️⃣ DFS + 백트래킹으로 최적화

1. (x, y) 좌표를 순차적으로 탐색하면서, 가능한 부메랑 배치 경우를 확인.
2. 배치 가능한 경우에만 부메랑을 배치하고 탐색을 진행.
3. 탐색이 끝난 후 다시 원래 상태로 되돌리는 백트래킹 적용.
4. 각 단계에서 최댓값을 갱신하여 최적의 해를 찾음.

---

📝 코드 구현

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

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;
    private static int[][] map;
    private static boolean[][] visited;

    private static int[][][] boomerang = {
        {{0, -1}, {0, 0}, {1, 0}},  // └ 모양
        {{0, -1}, {0, 0}, {-1, 0}}, // ┌ 모양
        {{-1, 0}, {0, 0}, {0, 1}},  // ┐ 모양
        {{0, 1}, {0, 0}, {1, 0}}    // ┘ 모양
    };

    private static int answer;

    public static void main(String[] args) throws IOException {
        setting();
        dfs(0, 0, 0);
        System.out.println(answer);
    }

    private static void dfs(int x, int y, int sum) {
        if (x == N - 1 && y == M) {
            answer = Math.max(answer, sum);
            return;
        }

        // 다음 좌표 계산
        x += y / M;
        y %= M;

        // 4가지 부메랑 배치 시도
        for (int i = 0; i < 4; i++) {
            int bx1 = x + boomerang[i][0][0];
            int by1 = y + boomerang[i][0][1];
            int bx2 = x + boomerang[i][1][0];
            int by2 = y + boomerang[i][1][1];
            int bx3 = x + boomerang[i][2][0];
            int by3 = y + boomerang[i][2][1];

            if (bx1 < 0 || bx1 >= N || by1 < 0 || by1 >= M || 
                bx2 < 0 || bx2 >= N || by2 < 0 || by2 >= M || 
                bx3 < 0 || bx3 >= N || by3 < 0 || by3 >= M) continue;

            if (visited[bx1][by1] || visited[bx2][by2] || visited[bx3][by3]) continue;

            // 방문 처리
            visited[bx1][by1] = visited[bx2][by2] = visited[bx3][by3] = true;
            int value = getValue(bx1, by1, bx2, by2, bx3, by3);

            dfs(x, y + 1, sum + value);

            // 백트래킹 (원상 복구)
            visited[bx1][by1] = visited[bx2][by2] = visited[bx3][by3] = false;
        }

        // 부메랑을 사용하지 않는 경우도 고려
        dfs(x, y + 1, sum);
    }

    private static int getValue(int bx1, int by1, int bx2, int by2, int bx3, int by3) {
        return map[bx1][by1] + map[bx2][by2] * 2 + map[bx3][by3];
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

---

🧐 코드 최적화 및 개선

🚀 1️⃣ DFS 탐색 순서 최적화

현재 dfs(x, y, sum) 에서 각 열(y)을 모두 탐색한 후 다음 행(x)으로 이동하는 방식을 사용.

• 기존: dfs(0, 0, 0) 시작 → y를 끝까지 탐색 → x 증가
• ✅ 개선: x += y / M; y %= M; 를 활용해 자동으로 다음 행으로 이동하도록 개선.

🚀 2️⃣ 방문 체크 최적화

• visited[][]를 통해 부메랑 배치 가능 여부를 빠르게 확인하여 불필요한 연산 제거.

🚀 3️⃣ 백트래킹 적용

• 부메랑 배치 후 원래 상태로 복구하는 백트래킹(visited[][] 복구) 적용.
• ✅ 최적의 경우만 탐색하여 불필요한 연산 감소.

---

✅ 코드 분석

함수	역할
dfs(x, y, sum)	현재 좌표 (x, y)에서 부메랑을 배치하면서 탐색
getValue(bx1, by1, bx2, by2, bx3, by3)	부메랑 배치 시 무기 점수 계산
setting()	입력 처리 및 초기화

---

🚀 시간복잡도 분석

• 최대 4^(N*M)의 경우의 수를 백트래킹으로 탐색
• ✅ 불가능한 배치는 즉시 가지치기(Pruning)하여 연산 감소
• N, M의 최대 크기가 5이므로 충분히 백트래킹으로 해결 가능

---

🎯 결론

✅ DFS + 백트래킹을 활용하여 최적의 부메랑 배치를 탐색
✅ 방문 체크(visited[][])를 활용하여 불필요한 연산 감소
✅ x += y / M; y %= M; 활용하여 탐색 흐름을 최적화