[백준] 18430. 무기 공학

문제 링크

[백준] 18430. 무기 공학

풀이 과정

백트래킹 문제입니다. 현재 좌표를 기준으로, 네 가지 부메랑 모양을 모두 확인하며, 가능한 경우엔 새로 계산되는 강도를 추가한 뒤 재귀 함수를 호출했습니다.

static void dfs(int x, int y, int sum) {
    if (y == M) {
        y = 0;
        x++;
    }

    if (x == N) {
        max = Math.max(max, sum);
        return;
    }

    if (isInRange(x, y - 1) && isInRange(x + 1, y) && !used[x][y] && !used[x][y - 1] && !used[x + 1][y]) {
        used[x][y] = used[x][y - 1] = used[x + 1][y] = true;
        dfs(x, y + 1, sum + 2 * map[x][y] + map[x][y - 1] + map[x + 1][y]);
        used[x][y] = used[x][y - 1] = used[x + 1][y] = false;
    }

    if (isInRange(x, y - 1) && isInRange(x - 1, y) && !used[x][y] && !used[x][y - 1] && !used[x - 1][y]) {
        used[x][y] = used[x][y - 1] = used[x - 1][y] = true;
        dfs(x, y + 1, sum + 2 * map[x][y] + map[x][y - 1] + map[x - 1][y]);
        used[x][y] = used[x][y - 1] = used[x - 1][y] = false;
    }

    if (isInRange(x - 1, y) && isInRange(x, y + 1) && !used[x][y] && !used[x - 1][y] && !used[x][y + 1]) {
        used[x][y] = used[x - 1][y] = used[x][y + 1] = true;
        dfs(x, y + 1, sum + 2 * map[x][y] + map[x - 1][y] + map[x][y + 1]);
        used[x][y] = used[x - 1][y] = used[x][y + 1] = false;
    }

    if (isInRange(x + 1, y) && isInRange(x, y + 1) && !used[x][y] && !used[x + 1][y] && !used[x][y + 1]) {
        used[x][y] = used[x + 1][y] = used[x][y + 1] = true;
        dfs(x, y + 1, sum + 2 * map[x][y] + map[x + 1][y] + map[x][y + 1]);
        used[x][y] = used[x + 1][y] = used[x][y + 1] = false;
    }

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

재귀에 사용된 dfs 메서드입니다.

2차원 배열 좌표를 전달 받으므로, 먼저 아래 과정을 거칩니다.

• y(열)값이 벗어나는 경우, 행은 증가시키고, 열은 첫 번째 열을 가리키도록 조정한다.
• x 값이 벗어나는 경우는 재귀 함수의 리턴 조건이 되며, 현재까지 계산한 부메랑 강도를 갱신한다.

다음으로 네 가지 부메랑 모양에 부합되면, used 배열을 통해 방문 처리를 한 후, 계산된 값으로 메서드를 재귀 호출합니다.

코드

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] used;
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        used = new boolean[N][M];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                map[i][j] = sc.nextInt();

        dfs(0, 0, 0);

        System.out.println(max);
    }

    static void dfs(int x, int y, int sum) {
        if (y == M) {
            y = 0;
            x++;
        }

        if (x == N) {
            max = Math.max(max, sum);
            return;
        }

        if (isInRange(x, y - 1) && isInRange(x + 1, y) && !used[x][y] && !used[x][y - 1] && !used[x + 1][y]) {
            used[x][y] = used[x][y - 1] = used[x + 1][y] = true;
            dfs(x, y + 1, sum + 2 * map[x][y] + map[x][y - 1] + map[x + 1][y]);
            used[x][y] = used[x][y - 1] = used[x + 1][y] = false;
        }

        if (isInRange(x, y - 1) && isInRange(x - 1, y) && !used[x][y] && !used[x][y - 1] && !used[x - 1][y]) {
            used[x][y] = used[x][y - 1] = used[x - 1][y] = true;
            dfs(x, y + 1, sum + 2 * map[x][y] + map[x][y - 1] + map[x - 1][y]);
            used[x][y] = used[x][y - 1] = used[x - 1][y] = false;
        }

        if (isInRange(x - 1, y) && isInRange(x, y + 1) && !used[x][y] && !used[x - 1][y] && !used[x][y + 1]) {
            used[x][y] = used[x - 1][y] = used[x][y + 1] = true;
            dfs(x, y + 1, sum + 2 * map[x][y] + map[x - 1][y] + map[x][y + 1]);
            used[x][y] = used[x - 1][y] = used[x][y + 1] = false;
        }

        if (isInRange(x + 1, y) && isInRange(x, y + 1) && !used[x][y] && !used[x + 1][y] && !used[x][y + 1]) {
            used[x][y] = used[x + 1][y] = used[x][y + 1] = true;
            dfs(x, y + 1, sum + 2 * map[x][y] + map[x + 1][y] + map[x][y + 1]);
            used[x][y] = used[x + 1][y] = used[x][y + 1] = false;
        }

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

    static boolean isInRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}