무기 공학 - 18430번

---

풀이 방법

부메랑을 만들기 위해 배열을 상하좌우로 1칸씩 늘려서 만들어서 사용했다. 부메랑을 만들 수 있는 부분은 visited를 false로 하고 주변부분은 true로 해주었다.

그리고 dfs를 이용해서 모든 경우의 수를 확인해보았다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;


public class Main {
    static int max = 0;
    static int N, M;
    static int[][] array;
    static int[][] way = {{0, -1, 1, 0}, {0, -1, -1, 0}, {0, 1, -1, 0}, {0, 1, 1, 0}};
    static boolean[][] visited;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        array = new int[N + 2][M + 2];
        visited = new boolean[N + 2][M + 2];
        for (int i = 0; i < visited.length; i++) {
            Arrays.fill(visited[i], true);
        }

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < M + 1; j++) {
                array[i][j] = Integer.parseInt(st.nextToken());
                visited[i][j] = false;
            }
        }

        dfs(0, 1, 1);
        System.out.println(max);
    }

    static void dfs(int sum, int x, int y) {
        if (sum > max)
            max = sum;

        for (int i = x; i < N + 1; i++) {
            for (int j = y; j < M + 1; j++) {
                for (int k = 0; k < 4; k++) {
                    if (!visited[i][j] && !visited[i + way[k][0]][j + way[k][1]] && !visited[i + way[k][2]][j + way[k][3]]) {
                        visited[i][j] = true;
                        visited[i + way[k][0]][j + way[k][1]] = true;
                        visited[i + way[k][2]][j + way[k][3]] = true;


                        if (y + 1 == M + 1)
                            dfs(sum + array[i][j] * 2 + array[i + way[k][0]][j + way[k][1]] + array[i + way[k][2]][j + way[k][3]], x + 1, 1);
                        else
                            dfs(sum + array[i][j] * 2 + array[i + way[k][0]][j + way[k][1]] + array[i + way[k][2]][j + way[k][3]], x, y + 1);

                        visited[i][j] = false;
                        visited[i + way[k][0]][j + way[k][1]] = false;
                        visited[i + way[k][2]][j + way[k][3]] = false;
                    }
                }
            }
        }

    }

}