[백준 18430, Java] 무기 공학

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

 

주어진 정보

1. 시간 제한 (2초): 약 2억번의 연산까지 가능
2. 메모리 제한 (256MB): int배열 기준 64백만 개의 원소 저장 가능
3. 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받음
4. 나무 재료의 크기가 작아 부메랑을 하나도 만들 수 없는 경우는 0을 출력

 

풀이 과정

모든 경우의 수를 탐색해야 하고, 이전 경우의 수가 다음 경우의 수에 영향을 준다. 

따라서 DFS 풀이를 생각할 수 있었다. 

 

나무 재료를 한칸씩 탐색하고, 해당 칸에서 부메랑을 만들지, 만든다면 어떻게 만들지 고민을 해야한다. 

 

해당 칸에서 부메랑을 만들 것인가?

이것은 해당 칸을 탐색했는지 안했는지를 검사해 탐색하지 않았다면 부메랑을 만들어야 한다. 

(여기서 부메랑을 안 만드는 방법이 답일 수도 있는 것 아닐까? 라는 생각을 했지만, 우리는 많은 연산을 빨리 할 수 있는 컴퓨터를 사용할 수 있기 때문에, 많은 경우의 수를 탐색할 수 있다!)

 

부메랑을 어떻게 만들 것인가?

문제에서 만들 수 있는 부메랑의 모양은 4가지다. 

이 모양을 실제로 구현할 때, 

다음과 같이 선언할 수 있다. 

반복문으로 부메랑 모양을 하나씩 선택해 강도를 확인하고 다음 dfs를 탐색한다. 

 

전체 코드

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[][] dx = {{0, 1}, {0, 1}, {0, -1}, {0, -1}};
    private static final int[][] dy = {{1, 0}, {-1, 0}, {-1, 0}, {1, 0}};
    private static int n, m;
    private static int maxValue;
    private static int[][] board;
    private static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        StringTokenizer 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());
            }
        }

        dfs(0, 0, 0);
        System.out.println(maxValue);
    }

    public static void dfs(int x, int y, int value) {
        if (y == m) {
            y = 0;
            x++;
        }

        if (x == n) {
            maxValue = Math.max(maxValue, value);
            return;
        }
        // 부메랑을 만들지 않는 경우
        dfs(x, y + 1, value);

        // 부메랑을 만드는 경우
        if (!visited[x][y]) {
            for (int i = 0; i < 4; i++) {
                int nx1 = x + dx[i][0];
                int ny1 = y + dy[i][0];
                int nx2 = x + dx[i][1];
                int ny2 = y + dy[i][1];

                if (inBounds(nx1, ny1) && inBounds(nx2, ny2) &&
                    !visited[nx1][ny1] && !visited[nx2][ny2]) {
                    visited[x][y] = visited[nx1][ny1] = visited[nx2][ny2] = true;
                    int newValue = value + board[x][y] * 2 + board[nx1][ny1] + board[nx2][ny2];
                    dfs(x, y + 1, newValue);
                    visited[x][y] = visited[nx1][ny1] = visited[nx2][ny2] = false;
                }
            }
        }
    }

    private static boolean inBounds(int nx, int ny) {
        return nx >= 0 && nx < n && ny >= 0 && ny < m;
    }
}