풀이 방법
부메랑을 만들기 위해 배열을 상하좌우로 1칸씩 늘려서 만들어서 사용했다. 부메랑을 만들 수 있는 부분은 visited를 false로 하고 주변부분은 true로 해주었다.
그리고 dfs를 이용해서 모든 경우의 수를 확인해보았다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int max = 0;
static int N, M;
static int[][] array;
static int[][] way = {{0, -1, 1, 0}, {0, -1, -1, 0}, {0, 1, -1, 0}, {0, 1, 1, 0}};
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
array = new int[N + 2][M + 2];
visited = new boolean[N + 2][M + 2];
for (int i = 0; i < visited.length; i++) {
Arrays.fill(visited[i], true);
}
for (int i = 1; i < N + 1; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < M + 1; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
visited[i][j] = false;
}
}
dfs(0, 1, 1);
System.out.println(max);
}
static void dfs(int sum, int x, int y) {
if (sum > max)
max = sum;
for (int i = x; i < N + 1; i++) {
for (int j = y; j < M + 1; j++) {
for (int k = 0; k < 4; k++) {
if (!visited[i][j] && !visited[i + way[k][0]][j + way[k][1]] && !visited[i + way[k][2]][j + way[k][3]]) {
visited[i][j] = true;
visited[i + way[k][0]][j + way[k][1]] = true;
visited[i + way[k][2]][j + way[k][3]] = true;
if (y + 1 == M + 1)
dfs(sum + array[i][j] * 2 + array[i + way[k][0]][j + way[k][1]] + array[i + way[k][2]][j + way[k][3]], x + 1, 1);
else
dfs(sum + array[i][j] * 2 + array[i + way[k][0]][j + way[k][1]] + array[i + way[k][2]][j + way[k][3]], x, y + 1);
visited[i][j] = false;
visited[i + way[k][0]][j + way[k][1]] = false;
visited[i + way[k][2]][j + way[k][3]] = false;
}
}
}
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
이동하기 - 11048번 (0) | 2021.10.19 |
---|---|
벽 부수고 이동하고 - 2206번 (0) | 2021.10.15 |
어두운 건 무서워 - 16507번 (0) | 2021.10.15 |
에너지 모으기 - 16198번 (0) | 2021.10.08 |
빙산 - 2573번 (0) | 2021.10.07 |