https://www.acmicpc.net/problem/18430
주어진 정보
- 시간 제한 (2초): 약 2억번의 연산까지 가능
- 메모리 제한 (256MB): int배열 기준 64백만 개의 원소 저장 가능
- 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받음
- 나무 재료의 크기가 작아 부메랑을 하나도 만들 수 없는 경우는 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;
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준 1043, Java] 거짓말 (0) | 2024.07.04 |
|---|---|
| [백준 1781, Java] 컵라면 (0) | 2024.07.04 |
| [백준 10800, Java] 컬러볼 (0) | 2024.07.04 |
| [백준 2212, Java] 센서 (0) | 2024.07.03 |
| [백준 17144, Java] 미세먼지 안녕! (0) | 2024.04.18 |