[DFS/백트래킹] 백준 18430번 무기공학 - JAVA

 

 

 

오랜만에 강적 문제를 만났다...

 

 

---

1. 출처

---

 

 

18430번: 무기 공학

 

 

 

 

---

2. 설계

---

 

혼자서는 설계하기 어려웠던 문제이다. 그래서 유튜브의 힘을 좀 빌렸다. 감사합니다 코데풀님...

 

 

 

영상을 보니 어느정도 설계 가닥이 잡혔다.

 

 

1) (0,0)부터 부메랑의 중심지를 잡는다.

 

2) 부메랑을 만드려고 하는 위치 3곳이 visited되었는지 체크한다.

 

3) 4개 모양의 부메랑 중 가능한 부메랑을 찾는다. 단, 한 중심지에서 모든 부메랑의 경우를 볼 것이다.

 

static int[][] boomerangType1 = {{0,-1},{1,0}};
static int[][] boomerangType2 = {{-1,0},{0,-1}};
static int[][] boomerangType3 = {{-1,0},{0,1}};
static int[][] boomerangType4 = {{1,0},{0,1}};

 

그림 순서대로 TYPE 1~4이다.

 

4) 부메랑의 강도를 변수 value에 넣어주고, 다음 중심지로 dfs를 연속한다.

 

5) 부메랑의 모든 타입을 다 dfs로 돌았다면 row == N && col == M인 지점으로 한 번더 dfs로 들어간다.

boomerang(order+1, value);

 

6) row == N && col == M이 되었을 때 value에 계산된 부메랑의 총합과 현재 최고 강도라고 계산한 result 변수를 비교하여 result에 max값을 저장한다.

 

 

 

 

새로 알게 된 점

여기서 내가 새로 알게 된 점은 row와 col을 구하는 방법이다.

2중 for문을 돌려 행렬을 체크해주는 대신 order이라는 변수를 써서 열로 나누고 나머지를 구해주었다.

int row = order/M;
int col = order%M;

 

 

 

예를 들면 (1,1)인 지점은 order가 4인것이다. (0부터 시작해서...)

 

order = 0 -> 행 : order / M = 0/3 = 0  ,   열 : order / M = 0%3 = 0

 

.

.

.

order = 4 -> 행 : order / M = 4/3 = 1  , 열 : order / M = 4%3 = 1

 

 

 

---

3. 전체 코드

---

 

import java.util.Scanner;

public class Main {

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

    static int[][] boomerangType1 = {{0,-1},{1,0}};
    static int[][] boomerangType2 = {{-1,0},{0,-1}};
    static int[][] boomerangType3 = {{-1,0},{0,1}};
    static int[][] boomerangType4 = {{1,0},{0,1}};

    static int result;

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

        map = new int[N][M];
        visited = new boolean[N][M];

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

        //입력 끝
        boomerang(0, 0);

        System.out.println(result);
        

    }

    public static void boomerang(int order, int value){//order은 0부터 시작

        if(order == N*M){
            result = Math.max(value, result);
            return;
        }

        //2중 for문을 도는 것과 같다.
        int row = order/M;
        int col = order%M;


        if(!visited[row][col]){

            //부메랑 방향 정하기
            if(inMap(new Direction(row+boomerangType1[0][0], col+boomerangType1[0][1]),new Direction(row+boomerangType1[1][0], col+boomerangType1[1][1]))){ //ㄱ
                //visited 체크
                visited[row][col] = true;
                visited[row+boomerangType1[0][0]][col+boomerangType1[0][1]] = true;
                visited[row+boomerangType1[1][0]][col+boomerangType1[1][1]] = true;
    
                //다음 부메랑 만들러 가기
                boomerang(order+1, value+map[row][col]*2 + map[row+boomerangType1[0][0]][col+boomerangType1[0][1]] + map[row+boomerangType1[1][0]][col+boomerangType1[1][1]]);
    
    
                //visited 체크 해제
                visited[row][col] = false;
                visited[row+boomerangType1[0][0]][col+boomerangType1[0][1]] = false;
                visited[row+boomerangType1[1][0]][col+boomerangType1[1][1]] = false;
            }
    
            if(inMap(new Direction(row+boomerangType2[0][0], col+boomerangType2[0][1]),new Direction(row+boomerangType2[1][0], col+boomerangType2[1][1]))){ //__ㅣ
                //visited 체크
                visited[row][col] = true;
                visited[row+boomerangType2[0][0]][col+boomerangType2[0][1]] = true;
                visited[row+boomerangType2[1][0]][col+boomerangType2[1][1]] = true;
    
                //다음 부메랑 만들러 가기
                boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType2[0][0]][col+boomerangType2[0][1]] + map[row+boomerangType2[1][0]][col+boomerangType2[1][1]]);
    
    
                //visited 체크 해제
                visited[row][col] = false;
                visited[row+boomerangType2[0][0]][col+boomerangType2[0][1]] = false;
                visited[row+boomerangType2[1][0]][col+boomerangType2[1][1]] = false;
            }
    
            if(inMap(new Direction(row+boomerangType3[0][0], col+boomerangType3[0][1]),new Direction(row+boomerangType3[1][0], col+boomerangType3[1][1]))){ //ㄴ
                //visited 체크
                visited[row][col] = true;
                visited[row+boomerangType3[0][0]][col+boomerangType3[0][1]] = true;
                visited[row+boomerangType3[1][0]][col+boomerangType3[1][1]] = true;
    
                //다음 부메랑 만들러 가기
                boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType3[0][0]][col+boomerangType3[0][1]] + map[row+boomerangType3[1][0]][col+boomerangType3[1][1]]);
    
    
                //visited 체크 해제
                visited[row][col] = false;
                visited[row+boomerangType3[0][0]][col+boomerangType3[0][1]] = false;
                visited[row+boomerangType3[1][0]][col+boomerangType3[1][1]] = false;
            }
    
            if(inMap(new Direction(row+boomerangType4[0][0], col+boomerangType4[0][1]),new Direction(row+boomerangType4[1][0], col+boomerangType4[1][1]))){ //|^^
                //visited 체크
                visited[row][col] = true;
                visited[row+boomerangType4[0][0]][col+boomerangType4[0][1]] = true;
                visited[row+boomerangType4[1][0]][col+boomerangType4[1][1]] = true;
    
                //다음 부메랑 만들러 가기
                boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType4[0][0]][col+boomerangType4[0][1]] + map[row+boomerangType4[1][0]][col+boomerangType4[1][1]]);
    
    
                //visited 체크 해제
                visited[row][col] = false;
                visited[row+boomerangType4[0][0]][col+boomerangType4[0][1]] = false;
                visited[row+boomerangType4[1][0]][col+boomerangType4[1][1]] = false;
            }
        }

        boomerang(order+1, value); //여기에 추가로 해주는 이유는 모든 부메랑 방향을 확인하고 나온 후 row==N && col==M 조건을 만족해야 return으로 max를 비교할 수 있기 때문이다.

    }


    public static boolean inMap(Direction d1, Direction d2){

        if(d1.row<0 || d1.row>=N || d1.col<0 || d1.col>=M) return false;
        if(visited[d1.row][d1.col]) return false;

        if(d2.row<0 || d2.row>=N || d2.col<0 || d2.col>=M) return false;
        if(visited[d2.row][d2.col]) return false;

        return true;
    }

    public static class Direction{
        int row;
        int col;

        public Direction(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
    
}

 

 

---

 

내일은 싸피가자마자 아메리카노다 ㅠ

그래도 뿌듯!