백준 18430 무기공학[JAVA]

🔗링크

18430 무기 공학 gold4

⚠️문제

---

공학자 길동이는 외부의 침략으로부터 마을을 지킬 수 있는 부메랑 무기를 개발하는 공학자다. 길동이는 부메랑 제작을 위한 고급 나무 재료를 구했다. 이 나무 재료는 NxM크기의 직사각형 형태이며 나무 재료의 부위마다 그 강도가 조금씩 다르다.

예를 들어 나무 재료의 크기가 2x3일 때는 다음과 같이 총 6칸으로 구성된다.

길동이는 이처럼 넓은 사각형 형태의 나무 재료를 잘라서 여러 개의 부메랑을 만들고자 한다. 그리고 부메랑은 항상 3칸을 차지하는 ‘ㄱ’모양으로 만들어야 한다. 따라서 부메랑의 가능한 모양은 다음과 같이 총 4가지다.

이때 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받는다. 위 그림에서 노란색으로 칠한 부분이 ‘중심이 되는 칸’이다. 예를 들어 앞선 예시에서는 다음과 같이 2개의 부메랑을 만들 수 있으며, 이때 만들어지는 부메랑들의 강도의 합은 46으로 이보다 강도의 합이 높아지는 경우는 없다.

또한 나무 재료의 특정 위치는 아예 사용하지 않아도 괜찮다. 예를 들어 앞선 예시에서 다음과 같이 1개의 부메랑만을 만들어도 괜찮다. 다만, 이렇게 만들게 되면 부메랑들의 강도의 합이 18이 되기 때문에 비효율적이다.

나무 재료의 형태와 각 칸의 강도가 주어졌을 때, 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내는 M개의 자연수 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ K ≤ 100)

 

출력

첫째 줄에 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력한다.

단, 나무 재료의 크기가 작아서 부메랑을 하나도 만들 수 없는 경우는 0을 출력한다.

🔍분석

---

DFS 백트래킹을 사용하여 해결하였다. 순서대로 순회하면서 부메랑을 만들어보고 다시 뒤로 가서 다른 모양의 부메랑을 만들어보면서 가능한 모든 경우의 수를 체크하여 최댓값을 뽑아내면 되는 문제라고 생각했다. 주의 할 점은 순회하면서 visited체크와 케이스를 여러 개로 나누어서 진행하면 실수가 많이 나올 것 같아 케이스를 나누는 부분을 좀 주의해서 구현하려고 노력했다.

---

1. 변수 선언은 아래 코드와 같이 하였다. 케이스의 가독성을 높이고 싶어서 int배열보다는 클래스 객체를 활용하였고, 강도를 저장하는 board와 해당 위치가 이미 부메랑에 사용된 부분인지 판단하는 visited배열을 선언했다.

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static int[][] board;
    static boolean[][] visited;
    static Coordinate[][] boomerangCase = {
            {new Coordinate(1, 0), new Coordinate(0, 0), new Coordinate(0, 1)},
            {new Coordinate(1, 0), new Coordinate(0, 0), new Coordinate(0, -1)},
            {new Coordinate(-1, 0), new Coordinate(0, 0), new Coordinate(0, 1)},
            {new Coordinate(-1, 0), new Coordinate(0, 0), new Coordinate(0, -1)},
    };

    static int result = 0;

 

2. 다음은 좌표 클래스를 만들었다. x, y 좌표를 멤버 변수로 선언하고, dfs에 다음 좌표를 계속하여 입력시킬 예정이라 다음 좌표를 계산하여 반환하는 메서드를 만들어 놓았다.

class Coordinate {
    int x;
    int y;

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

    public Coordinate nextCoordinate(int m){
        int x2 = x;
        int y2 = y;
        y2++;
        if(y2 >= m){
            x2++;
            y2 = 0;
        }
        return new Coordinate(x2, y2);
    }
}

 

3. dfs기능을 구현했다. 0,0 좌표부터 시작하여 현재 좌표가 중심이 되는 부메랑을 만들 수 있는 지 우선 확인한다.

for (Coordinate coordinate : coordinates) {
  if (!checkInside(cur.x + coordinate.x, cur.y + coordinate.y) || visited[cur.x + coordinate.x][cur.y + coordinate.y]) {
    able = false;
    break;
  }
}

4. 가능하다면 해당 부메랑 위치의 강도를 모두 더하고 visited(이미 부메랑을 만든 위치)도 true로 계산하여 반환한다. 이후, 다음 위치로 가서 부메랑을 만들어야 하기 때문에 현재 실행되는 함수를 재귀적으로 실행시킨다.

5.계산은 재귀적으로 계산한 다음 함수에 맡겼기 때문에 계산이 끝났을 때, 현재 체크했던 강도의 값과 만들었던 위치를 복귀 시켜야 한다. (다른 모양의 부메랑도 계산해야 하기 때문)

6. 현재 위치가 중심이 되는 부메랑이 포함되지 않더라도 최댓값이 되는 경우가 있으므로 현재 위치가 중심이 되는 부메랑의 경우가 끝났으면 현재 위치를 그냥 스킵하고 다음 위치를 계산하는 로직도 있어야 한다. 그러므로 현재 위치를 계산하지 않는 재귀 함수도 포함시킨다. 

public static void makeBoomerang(Coordinate cur, int totalStrength) {

        if(cur.x >= N){
            result = Math.max(result, totalStrength);
            return;
        }

        for (Coordinate[] coordinates : boomerangCase) {

            boolean able = true;

            for (Coordinate coordinate : coordinates) {
                if (!checkInside(cur.x + coordinate.x, cur.y + coordinate.y) || visited[cur.x + coordinate.x][cur.y + coordinate.y]) {
                    able = false;
                    break;
                }
            }

            if(able){
                for (Coordinate coordinate : coordinates) {
                    if(coordinate.x == 0 && coordinate.y == 0){
                        totalStrength += board[cur.x + coordinate.x][cur.y + coordinate.y] * 2;
                    }else{
                        totalStrength += board[cur.x + coordinate.x][cur.y + coordinate.y];
                    }

                    visited[cur.x + coordinate.x][cur.y + coordinate.y] = true;
                }

                makeBoomerang(cur.nextCoordinate(M), totalStrength);

                for (Coordinate coordinate : coordinates) {
                    if(coordinate.x == 0 && coordinate.y == 0){
                        totalStrength -= board[cur.x + coordinate.x][cur.y + coordinate.y] * 2;
                    }else{
                        totalStrength -= board[cur.x + coordinate.x][cur.y + coordinate.y];
                    }

                    visited[cur.x + coordinate.x][cur.y + coordinate.y] = false;
                }
            }
        }
        makeBoomerang(cur.nextCoordinate(M), totalStrength);
    }

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

---

✔전체 코드

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

class Main {

    //dfs
    //신경쓸 점: 케이스 나누기
    //          탈출 조건

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static int[][] board;
    static boolean[][] visited;
    static Coordinate[][] boomerangCase = {
            {new Coordinate(1, 0), new Coordinate(0, 0), new Coordinate(0, 1)},
            {new Coordinate(1, 0), new Coordinate(0, 0), new Coordinate(0, -1)},
            {new Coordinate(-1, 0), new Coordinate(0, 0), new Coordinate(0, 1)},
            {new Coordinate(-1, 0), new Coordinate(0, 0), new Coordinate(0, -1)},
    };

    static int result = 0;

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

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

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

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

        makeBoomerang(new Coordinate(0, 0), 0);

        System.out.println(result);
    }

    public static void makeBoomerang(Coordinate cur, int totalStrength) {

        if(cur.x >= N){
            result = Math.max(result, totalStrength);
            return;
        }

        for (Coordinate[] coordinates : boomerangCase) {

            boolean able = true;

            for (Coordinate coordinate : coordinates) {
                if (!checkInside(cur.x + coordinate.x, cur.y + coordinate.y) || visited[cur.x + coordinate.x][cur.y + coordinate.y]) {
                    able = false;
                    break;
                }
            }

            if(able){
                for (Coordinate coordinate : coordinates) {
                    if(coordinate.x == 0 && coordinate.y == 0){
                        totalStrength += board[cur.x + coordinate.x][cur.y + coordinate.y] * 2;
                    }else{
                        totalStrength += board[cur.x + coordinate.x][cur.y + coordinate.y];
                    }

                    visited[cur.x + coordinate.x][cur.y + coordinate.y] = true;
                }

                makeBoomerang(cur.nextCoordinate(M), totalStrength);

                for (Coordinate coordinate : coordinates) {
                    if(coordinate.x == 0 && coordinate.y == 0){
                        totalStrength -= board[cur.x + coordinate.x][cur.y + coordinate.y] * 2;
                    }else{
                        totalStrength -= board[cur.x + coordinate.x][cur.y + coordinate.y];
                    }

                    visited[cur.x + coordinate.x][cur.y + coordinate.y] = false;
                }
            }
        }
        makeBoomerang(cur.nextCoordinate(M), totalStrength);
    }

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

class Coordinate {
    int x;
    int y;

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

    public Coordinate nextCoordinate(int m){
        int x2 = x;
        int y2 = y;
        y2++;
        if(y2 >= m){
            x2++;
            y2 = 0;
        }
        return new Coordinate(x2, y2);
    }
}

 

😄결과

 

결과를 보면 다른 결과에 비해 메모리가 두 배정도 더 컸다. 아마 객체를 사용함으로 메모리가 증가하고 다음 좌표를 계산할 때 계속해서 객체를 생성하여 반환했던 점이 좀 크게 작용했던 것 같다. 이를 수정하면 메모리를 줄일 수 있을 것이다.

→ 해당 부문만 수정 했을 때 결과

** dfs나 재귀 관련 다룰 때 객체 복사 주의하기