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

문제 링크

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

문제 풀이

부메랑은 기준점을 기준으로 총 4방향으로 있을수가 있다. 이 4방향이 마치 함수의 1사분면 2사분면 과 같은 모습이기에 각 모양에 대해

static int[][] dir = {{-1, 0, 0, 1}, {-1, 0, 0, -1}, {1, 0, 0, -1}, {1, 0, 0, 1}};

와 같이 접근했다.
ex) 1사분면의 모양 : {-1,0,0,1} 인데 기준점을 중심으로 위의 칸은 y축,x축으로 (-1,0)만큼 기준점을 중심으로 오른쪽 칸은 y축, x축으로 (0,1)만큼 이동한것이므로
1사분면을 나타내는 모양을 {-1,0,0,1}로 하기로 했으면 이와 같은 방법으로 2,3,4사분면도 표시했다.

기준점의 위치를 저장하는 class인 Node가 있는데
기준점의 y,x축을 저장하며, 기준점이 어느 사분면의 모양인지를 저장할 point를 같이 가지고 있다. ex) point=0 ->1사분면

가로나 세로의 길이가 1인경우에는 부메랑을 만들수 없으므로
아래의 조건을 통해서 값을 분기시킨다.

        if ( !(n == 1 || m==1)) {
            dfs(0, 0, new ArrayList(), chk);
        }
        System.out.println(answer);

dfs에는 현재의 y,x좌표가 들어가 있으며, 해당 dfs에서 만든 부메랑의 정보들을 arraylist를 통해서 저장했으며 이미 사용한 칸에 대한 중복 체크를 하기 위해 chk를 같이 넣고 돌렸다.
우선 dir의 값들을 더했을때 배열의 범위를 초과하지 않는지를 먼저 체크 후에
그 칸들이 중복되었는지 중복체크까지 통과하면
그값들은 부메랑을 만들 수 있다는 해당 좌표에 대해서 1~4사분면중에 갈수 있는 경우가 있는경우 그 값을 arraylist에 저장하고, 중복체크값을 true로 바꿔주고 dfs에 인자로 담아서 넘겨주었다.

for (int k = 0; k < 4; k++) {
            if (now_y + dir[k][0] >= 0 && now_y + dir[k][0] < n
                    && now_y>=0 && now_y<n
                    && now_x>=0 && now_x<m
                    && now_x + dir[k][3] >= 0 && now_x + dir[k][3] < m) {
                if (!chk[now_y][now_x] && !chk[now_y + dir[k][0]][now_x + dir[k][1]] && !chk[now_y + dir[k][2]][now_x + dir[k][3]]) {
                    chk[now_y][now_x] = true;
                    chk[now_y + dir[k][0]][now_x + dir[k][1]] = true;
                    chk[now_y + dir[k][2]][now_x + dir[k][3]] = true;
                    arr.add(new Node(now_y, now_x, k));
                    if (now_x == m - 1 && now_y == n - 1) {
                        dfs(now_y + 1, now_x + 1, arr, chk);
                        pass = false;
                    } else if (now_x == m - 1) {
                        dfs(now_y + 1, 0, arr, chk);
                    } else {
                        dfs(now_y, now_x + 1, arr, chk);
                    }
                    arr.remove(arr.size()-1);
                    chk[now_y][now_x] = false;
                    chk[now_y + dir[k][0]][now_x + dir[k][1]] = false;
                    chk[now_y + dir[k][2]][now_x + dir[k][3]] = false;
                }
            }
        }

만약에 해당 좌표에서 만들수 있는 모양이 없는 경우에는 다음 좌표로 이동시킨다.

        if(pass){
            if (now_x == m - 1 && now_y == n - 1) {
                dfs(now_y + 1, now_x + 1, arr, chk);
            } else if (now_x == m - 1) {
                dfs(now_y + 1, 0, arr, chk);
            } else {
                dfs(now_y, now_x + 1, arr, chk);
            }
        }

y,x가 n,m값이 돠면 더이상 체크할 수 없으므로
부메랑의 값들을 더해준다. 기준점은 *2 를 해준다.

        if (y == n && x == m) {
            int len = arr.size();
            int sum = 0;
            //System.out.println(arr.toString());
            for (int i = 0; i < len; i++) {
                int now_y = arr.get(i).y;
                int now_x = arr.get(i).x;
                int now_point = arr.get(i).point;
                sum += map[now_y][now_x]*2 +
                        map[now_y + dir[now_point][0]][now_x + dir[now_point][1]] +
                        map[now_y + dir[now_point][2]][now_x + dir[now_point][3]];
                //System.out.println(map[now_y][now_x]+"+"+map[now_y + dir[now_point][0]][now_x + dir[now_point][1]]+"+"+map[now_y + dir[now_point][2]][now_x + dir[now_point][3]]);
            }
            //System.out.println("!!"+sum);
            answer = Math.max(answer, sum);
            return;
        }

코드

import java.util.*;


public class Main {

    static int n;
    static int m;

    static int[][] map;

    //1사분면  2사분면 3사분면  4사분면
    static int[][] dir = {{-1, 0, 0, 1}, {-1, 0, 0, -1}, {1, 0, 0, -1}, {1, 0, 0, 1}};

    static class Node {
        int y;
        int x;
        int point;

        public Node(int y, int x, int point) {
            this.y = y;
            this.x = x;
            this.point = point;
        }


        public String toString(){
            return "y : "+y +" x : "+x +"  "+(point+1)+"사분면";
        }
    }

    static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        map = new int[n][m];
        boolean[][] chk = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }


        if ( !(n == 1 || m==1)) {
            dfs(0, 0, new ArrayList(), chk);
        }
        System.out.println(answer);

    }

    public static void dfs(int y, int x, ArrayList<Node> arr, boolean[][] chk) {
        if (y == n && x == m) {
            int len = arr.size();
            int sum = 0;
            //System.out.println(arr.toString());
            for (int i = 0; i < len; i++) {
                int now_y = arr.get(i).y;
                int now_x = arr.get(i).x;
                int now_point = arr.get(i).point;
                sum += map[now_y][now_x]*2 +
                        map[now_y + dir[now_point][0]][now_x + dir[now_point][1]] +
                        map[now_y + dir[now_point][2]][now_x + dir[now_point][3]];
                //System.out.println(map[now_y][now_x]+"+"+map[now_y + dir[now_point][0]][now_x + dir[now_point][1]]+"+"+map[now_y + dir[now_point][2]][now_x + dir[now_point][3]]);
            }
            //System.out.println("!!"+sum);
            answer = Math.max(answer, sum);
            return;
        }


        int now_y = y;
        int now_x = x;
        boolean pass = true;
        for (int k = 0; k < 4; k++) {
            if (now_y + dir[k][0] >= 0 && now_y + dir[k][0] < n
                    && now_y>=0 && now_y<n
                    && now_x>=0 && now_x<m
                    && now_x + dir[k][3] >= 0 && now_x + dir[k][3] < m) {
                if (!chk[now_y][now_x] && !chk[now_y + dir[k][0]][now_x + dir[k][1]] && !chk[now_y + dir[k][2]][now_x + dir[k][3]]) {
                    chk[now_y][now_x] = true;
                    chk[now_y + dir[k][0]][now_x + dir[k][1]] = true;
                    chk[now_y + dir[k][2]][now_x + dir[k][3]] = true;
                    arr.add(new Node(now_y, now_x, k));
                    if (now_x == m - 1 && now_y == n - 1) {
                        dfs(now_y + 1, now_x + 1, arr, chk);
                        pass = false;
                    } else if (now_x == m - 1) {
                        dfs(now_y + 1, 0, arr, chk);
                    } else {
                        dfs(now_y, now_x + 1, arr, chk);

                    }
                    arr.remove(arr.size()-1);
                    chk[now_y][now_x] = false;
                    chk[now_y + dir[k][0]][now_x + dir[k][1]] = false;
                    chk[now_y + dir[k][2]][now_x + dir[k][3]] = false;
                }
            }

        }

        if(pass){
            if (now_x == m - 1 && now_y == n - 1) {
                dfs(now_y + 1, now_x + 1, arr, chk);
            } else if (now_x == m - 1) {
                dfs(now_y + 1, 0, arr, chk);
            } else {
                dfs(now_y, now_x + 1, arr, chk);
            }
        }

    }
}