링크
https://www.acmicpc.net/problem/14500
문제 설명
정답률 36.588%
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력 예제
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1출력 예제
19풀이
주어진 2차원 배열에서 테트로미노 모양에 해당되는 수들의 합이 최댓값일 때를 구해야 한다.
각 테트로미노는 특정 좌표에서 다음과 같이 움직일 수 있다.
하지만 ㅜ 모양의 테트로미노는 하나의 선으로 탐색을 할 수 없기 때문에 따로 고려해야 한다. 우선 ㅜ 모양을 제외하고 생각해보면 하나의 선으로 탐색하는 것은 결국 DFS를 이용하여 탐색할 수 있다. 깊이가 4가 될 때까지 탐색하면 각 테트로미노 모양에 부합한다.
모든 좌표에 대해 탐색을 해야되기 때문에 각 좌표에 대해 DFS를 진행한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
dfs(i, j, paper[i][j], 1);
visited[i][j] = false;
}
}DFS 메서드는 깊이가 4가 될 때 합의 최댓값을 구하도록 한다.
static void dfs(int r, int c, int sum, int depth) {
if (depth == 4) {
maxSum = Math.max(maxSum, sum);
return;
}
for (int i = 0; i < 4; i++) {
int nextR = r + dr[i];
int nextC = c + dc[i];
if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) {
continue;
}
if (!visited[nextR][nextC]) {
visited[nextR][nextC] = true;
dfs(nextR, nextC, sum + paper[nextR][nextC], depth + 1);
visited[nextR][nextC] = false;
}
}
}이제 ㅜ 모양에 대해 생각해봐야 하는데 다음과 같이 방법이 있다.
- DFS가 완료된 후 ㅜ 모양에 대해 따로 합을 구함
- DFS 탐색 중에 깊이가 2일 때 다음 좌표에 대해 재귀를 호출하는 것이 아니라 현재 좌표로 재귀 호출 진행
우선 ㅜ 모양에 대해 따로 합을 구하기 위해서 다음과 같이 메서드를 작성한다.
static void checkExtraShape(int r, int c) {
//ㅜ 모양 테트로미노는 4가지 변형이 있으므로 이를 처리
int sum;
//ㅏ, ㅓ 모양
if (r >= 1 && r <= N - 2) {
//ㅏ
if (c <= M - 2) {
sum = paper[r][c] + paper[r - 1][c] + paper[r + 1][c] + paper[r][c + 1];
maxSum = Math.max(maxSum, sum);
}
//ㅓ
if (c >= 1) {
sum = paper[r][c] + paper[r - 1][c] + paper[r + 1][c] + paper[r][c - 1];
maxSum = Math.max(maxSum, sum);
}
}
//ㅜ, ㅗ 모양
if (c >= 1 && c <= M - 2) {
//ㅜ
if (r <= N - 2) {
sum = paper[r][c] + paper[r][c - 1] + paper[r][c + 1] + paper[r + 1][c];
maxSum = Math.max(maxSum, sum);
}
//ㅗ
if (r >= 1) {
sum = paper[r][c] + paper[r][c - 1] + paper[r][c + 1] + paper[r - 1][c];
maxSum = Math.max(maxSum, sum);
}
}
}그리고 DFS 탐색 완료 후 메서드를 호출한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
dfs(i, j, paper[i][j], 1);
visited[i][j] = false;
checkExtraShape(i, j);
}
}DFS 탐색 중에 구할 때는 재귀를 호출하는 부분을 다음과 같이 수정한다.
if (!visited[nextR][nextC]) {
if (depth == 2) {
visited[nextR][nextC] = true;
dfs(r, c, sum + paper[nextR][nextC], depth + 1);
visited[nextR][nextC] = false;
}
visited[nextR][nextC] = true;
dfs(nextR, nextC, sum + paper[nextR][nextC], depth + 1);
visited[nextR][nextC] = false;
}코드
//백준
public class Main {
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static int N;
static int M;
static int maxSum;
static boolean[][] visited;
static int[][] paper;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //세로
M = Integer.parseInt(st.nextToken()); //가로
paper = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
paper[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
dfs(i, j, paper[i][j], 1);
visited[i][j] = false;
checkExtraShape(i, j);
}
}
System.out.println(maxSum);
}
static void dfs(int r, int c, int sum, int depth) {
if (depth == 4) {
maxSum = Math.max(maxSum, sum);
return;
}
for (int i = 0; i < 4; i++) {
int nextR = r + dr[i];
int nextC = c + dc[i];
if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) {
continue;
}
if (!visited[nextR][nextC]) {
if (depth == 2) {
visited[nextR][nextC] = true;
dfs(r, c, sum + paper[nextR][nextC], depth + 1);
visited[nextR][nextC] = false;
}
visited[nextR][nextC] = true;
dfs(nextR, nextC, sum + paper[nextR][nextC], depth + 1);
visited[nextR][nextC] = false;
}
}
}
}
백엔드