[백준] 무기 공학 G4 - 백트랙킹 JAVA

1. 문제

 

 

2. 접근

부메랑을 만들기 위해서는 3 depth가 필요하고 부메랑을 만든 결과가 이어지면서 탐색을 진행해야한다.

-> 백트랙킹 이용

 

어떤 데이터가 필요?

-> 완성된 부메랑과 방문한 좌표를 저장할 boolean 배열, depth

 

depth가 3이 되어서 부메랑이 만들어진 후엔?

-> 새로운 부메랑을 만들어야 함. 하지만 다음 좌표의 기준이 모호함. 전체 좌표 중 방문 안한 모든 좌표?

이러면 처음 함수를 호출할 때랑 달라지는 것이 없어짐

 

--> 시도 했지만 시간 초과

 

 

다른 방법

 

부메랑을 만들 때 DFS 방식으로 depth가 3이 될 때까지 계속 호출하는 것이 아닌, 부메랑이 만들어질 수 있는지 바로 체크하기

-> 현재 좌표를 제외하면 딱 2좌표만 확인하면 되기 때문에 가능함. 그리고 이 방법은 부메랑의 depth를 따로 관리를 하지 않아도 되어서 편함

-> 즉 한 번 함수가 실행되면 3개의 좌표를 동시에 방문하여 부메랑을 만듦. 

-> depth는 1씩 증가하며 N*M개가 될 때까지 반복

 

현재 좌표가 방문한 노드라면

-> pos+1, sum은 그대로로 다음 좌표로

 

현재 좌표가 방문하지 않은 노드라면

-> 현재 위치에 4종류의 부메랑이 만들어질 수 있는지 확인

-> 만들 수 있다면 3 좌표를 방문 처리하고, pos+1, 부메랑 점수를 더해서 재귀 호출

private static void createBumerang(boolean[][] isVisited, int pos, int sum){
    if(pos == N*M){
        max = Math.max(sum, max);
        return;
    }

    int r = pos/M;
    int c = pos%M;

    if(isVisited[r][c]){
        createBumerang(isVisited, pos+1, sum);
    }
    else{
        isVisited[r][c] = true;

        for(int k=0; k<4; k++){
            int nr = r + dir[k][0][1];
            int nc = c + dir[k][1][1];

            if(nr < 0 || nr >= N || nc <0 || nc >= M || isVisited[nr][nc])
                continue;

            int nnr = r + dir[k][0][2];
            int nnc = c + dir[k][1][2];

            if(nnr < 0 || nnr >= N || nnc <0 || nnc >= M || isVisited[nnr][nnc])
                continue;

            isVisited[nr][nc] = true;
            isVisited[nnr][nnc] = true;

            createBumerang(isVisited, pos +1, sum + map[r][c] + (map[nr][nc])*2 + map[nnr][nnc]);

            isVisited[nr][nc] = false;
            isVisited[nnr][nnc] = false;
        }

        isVisited[r][c] = false;
        createBumerang(isVisited, pos+1, sum);
    }

 

 

3. 전체 코드

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


class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int max = 0;
    static int N, M;
    static int [][] map;
    static int dir [][][] = {
        { {0, 0, 1}, {0, 1, 1} },
        { {0, 0, -1}, {0, 1,1}},
        { {0, 1, 1}, {0, 0, 1} },
        { {0, 0, 1}, {0, -1,-1}}
    };

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[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());
            }
        }

        boolean [][] isVisited = new boolean[N][M];
        createBumerang(isVisited, 0,0);

        System.out.println(max);
    }

    private static void createBumerang(boolean[][] isVisited, int pos, int sum){
        if(pos == N*M){
            max = Math.max(sum, max);
            return;
        }

        int r = pos/M;
        int c = pos%M;

        if(isVisited[r][c]){
            createBumerang(isVisited, pos+1, sum);
        }
        else{
            isVisited[r][c] = true;

            for(int k=0; k<4; k++){
                int nr = r + dir[k][0][1];
                int nc = c + dir[k][1][1];

                if(nr < 0 || nr >= N || nc <0 || nc >= M || isVisited[nr][nc])
                    continue;

                int nnr = r + dir[k][0][2];
                int nnc = c + dir[k][1][2];

                if(nnr < 0 || nnr >= N || nnc <0 || nnc >= M || isVisited[nnr][nnc])
                    continue;

                isVisited[nr][nc] = true;
                isVisited[nnr][nnc] = true;

                createBumerang(isVisited, pos +1, sum + map[r][c] + (map[nr][nc])*2 + map[nnr][nnc]);

                isVisited[nr][nc] = false;
                isVisited[nnr][nnc] = false;
            }

            isVisited[r][c] = false;
            createBumerang(isVisited, pos+1, sum);
        }

    }
}