[백준] 테트로미노 - GOLD IV 14500번
접근
- dfs
풀이
Class 3에 남았던 마지막 문제로 대미를 장식하는 만큼 정말 많은 제출로 통과를 시도했고 이때까지 백준에서 푼 문제 중에 가장 많은 시간을 사용했던 문제이다. 문제의 내용은 값이 적혀있는 2차원 배열에 테트리스에서 나오는 모양들의 블록을 배치했을 때 각 자리 값들의 합이 가장 클 때의 값이 얼마인지 구하는 문제이다. 문제는 모든 경로를 깊게 탐색하여 살펴봐야 하기 때문에 dfs를 사용해서 풀어주었다. 문제를 풀긴 했지만 원하던 대로 시원하게 풀지 못했고 일단 크게 겪었던 이슈에 대해서부터 언급하고 넘어가겠다.
1. T 모양 블록 처리
처음 문제를 풀 때 단순 dfs를 사용하면 모든 경로를 깊숙하게 탐색을 하기 때문에 4칸의 깊이 제한을 두면 바로 풀어질 줄 알았다. 그러나 dfs만 단독으로 사용하는 경우 T자 블록 처리가 불가능했다. dfs 알고리즘을 따라 블록 생성이 진행될 경우 한 방향으로 진행하는 모양은 모두 체크가 가능하지만 T 블록처럼 나아가는 방향이 2개가 되는 경우 체크가 불가능하다. 그렇기 때문에 T 블록에 대한 체크는 따로 진행을 해주어야 한다.
2. 방문체크
dfs 또한 방문체크가 성능을 좌우하는 매우 중요한 요소 중 하나이다. 그런데 bfs의 경우 다시 진행했던 길로 돌아가는 경우가 없기 때문에 하나의 방문체크 배열로 모든 탐색을 진행할 수 있다. 그러나 dfs는 해당 경로 탐색이 끝나면 이전으로 돌아가 다른 경로를 탐색해야 하기 때문에 각 진행하는 단계마다 독립된 방문체크가 필요하다. 보통 dfs나 bfs를 구현할 때 재귀함수 보단 큐랑 스택을 사용해 구현하는 것을 선호하기 때문에 스택에 들어갈 객체 필드에 독립적인 방문체크 배열이 존재해야 했다. 그렇게 배열의 정보를 넘겨받는 경우 = 연산자로 할당하게 되면 참조값을 넘기기 때문에 독립적인 배열을 위해선 깊은 복사를 진행해주어야 했다. 여기서 생겼던 문제로 이번 문제에 사용되는 배열은 2차원 배열로 깊은 복사를 위해선 참조를 넘기는 것이 아니라 직접 값을 할당해줘야 한다는 소리다. 그렇다면 깊은 복사를 진행하는 2차원 배열의 크기만큼 반복 연산이 일어나게 되고 이 연산은 스택에 새로운 상태가 추가될 때 매번 일어나게 되는 것이다. 기본적으로 반복량이 많은 dfs에 매번 2차원 배열의 깊은 복사가 일어나다 보니 바로 시간초과가 발생하였다. 그렇게 방문체크 방식을 바꿔 비트마스킹을 사용한 방식으로 변경해 봤으나 13프로에서 실패가 떠 결국 원인을 찾지 못하고 재귀 함수를 사용하는 방식으로 변경했다.
private static final int[] dx = {0, 0, 1, -1};
private static final int[] dy = {1, -1, 0, 0};
private static int maxSum = 0;기본적인 상하좌우 움직임을 위한 배열과 최댓값으로 사용할 변수도 전역으로 선언했다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] NM = br.readLine().split(" ");
int N = Integer.parseInt(NM[0]);
int M = Integer.parseInt(NM[1]);
int[][] paper = new int[N][M];
for (int n = 0; n < N; n++) {
paper[n] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
boolean[][] isVisited = new boolean[N][M];값을 입력 받고 배열로 변경하는 부분과 방문체크를 위한 배열을 선언하는 부분이다. 2차원 배열의 경우 스트림을 사용해 간단하게 변환해 주었다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
isVisited[i][j] = true;
dfs(i, j, 1, paper[i][j], isVisited, N, M, paper);
isVisited[i][j] = false;
checkTShape(i, j, N, M, paper);
}
}dfs를 사용한 메서드와 T자 블록체크를 위한 메서드를 따로 분리해 주었다. 모든 좌표를 돌며 체크하게 된다.
private static void dfs(int x, int y, int count, int sum, boolean[][] isVisited, int N, int M, int[][] paper) {
if (count == 4) {
maxSum = Math.max(maxSum, sum);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || isVisited[nx][ny]) {
continue;
}
isVisited[nx][ny] = true;
dfs(nx, ny, count + 1, sum + paper[nx][ny], isVisited, N, M, paper);
isVisited[nx][ny] = false;
}
}우선 dfs 메서드이다. 블록의 크기는 4로 깊이가 4가 될 경우 종료되고 각 위치를 이동하며 좌표가 범위 내이고 방문하지 않았다면 다음 상태로 넘어간다. 재귀 함수로 구현할 땐 함수 호출이 스택에 쌓여 해당 위치의 방문이 true로 변경된 이후 또다시 dfs 함수 재귀호출로 해당 단계에서 갈 수 있는 깊은 경로를 다 탐색한 뒤에 방문을 다시 false 처리하기 때문에 스택을 사용할 때처럼 독립적인 방문배열 같은 게 필요 없다. 스택의 경우 다음 상태로 전이되기 위해선 스택에 쌓여있는 다음 위치를 뽑아내 while문을 돌려야 하기 때문에 다음 상태 추가 후 다시 방문을 false로 변경하는 코드를 해당 경로 탐색이 진행되기 전에 수행할 수밖에 없다. 그래서 스택에 들어가는 객체가 독립적인 방문배열을 가져야 중복과 잘못된 경로를 피할 수 있지만 재귀함수의 경우 false 변경 전 모든 경로 탐색이 다 진행되기 때문에 코드상으론 훨씬 간결해지는 것이다. 그러나 재귀 함수를 사용하는 경우 스택을 사용하는 것보다 스택 오버플로우 발생 가능성이 높다. 스택을 사용하는 경우는 해당 단계 탐색이 끝날 때마다 스택에서 제거되고 다음 단계가 삽입되지만 재귀함수의 경우 그렇지 않기 때문이다.
private static void checkTShape(int x, int y, int N, int M, int[][] paper) {
for (int i = 0; i < 4; i++) {
int sum = paper[x][y];
for (int d = 0; d < 4; d++) {
if (d == i) continue;
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
continue;
}
sum += paper[nx][ny];
}
maxSum = Math.max(maxSum, sum);
}
}다음으로 T 블록을 체크하는 메서드이다. 해당 코드는 게시판을 둘러보다 어떤 코드를 참조한 것으로 해당 위치에서 3방향으로 블록을 더해 T 모양을 만드는 코드이다. 2중 반복으로 한 방향씩 제외하고 블록을 더해줘 T 모양을 회전해서 만들어지는 모든 경우에 대해 체크한다. dfs메서드와 T 블록체크 메서드로 얻어진 최댓값을 결과로 반환하게 된다.
전체 코드
import java.io.*;
import java.util.*;
public class Main {
private static final int[] dx = {0, 0, 1, -1};
private static final int[] dy = {1, -1, 0, 0};
private static int maxSum = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] NM = br.readLine().split(" ");
int N = Integer.parseInt(NM[0]);
int M = Integer.parseInt(NM[1]);
int[][] paper = new int[N][M];
for (int n = 0; n < N; n++) {
paper[n] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
boolean[][] isVisited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
isVisited[i][j] = true;
dfs(i, j, 1, paper[i][j], isVisited, N, M, paper);
isVisited[i][j] = false;
checkTShape(i, j, N, M, paper);
}
}
System.out.println(maxSum);
br.close();
}
private static void dfs(int x, int y, int count, int sum, boolean[][] isVisited, int N, int M, int[][] paper) {
if (count == 4) {
maxSum = Math.max(maxSum, sum);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || isVisited[nx][ny]) {
continue;
}
isVisited[nx][ny] = true;
dfs(nx, ny, count + 1, sum + paper[nx][ny], isVisited, N, M, paper);
isVisited[nx][ny] = false;
}
}
private static void checkTShape(int x, int y, int N, int M, int[][] paper) {
for (int i = 0; i < 4; i++) {
int sum = paper[x][y];
for (int d = 0; d < 4; d++) {
if (d == i) continue;
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
continue;
}
sum += paper[nx][ny];
}
maxSum = Math.max(maxSum, sum);
}
}
}스택을 사용해 구현해보려 했으나 끝내 실패했다. 방문체크를 어떻게 효율적으로 수행할 수 있는지가 관건인 거 같은데 답을 찾아내진 못한 거 같다.
이로써 클래스 3의 문제도 모두 해결했다.
'알고리즘 > 코딩테스트-백준' 카테고리의 다른 글
| [백준] 최소비용 구하기 JAVA (0) | 2024.10.04 |
|---|---|
| [백준] A -> B JAVA (0) | 2024.10.03 |
| [백준] 뱀과 사다리 게임 JAVA (0) | 2024.10.01 |
| [백준] 적록색약 JAVA (0) | 2024.09.30 |
| [백준] 토마토 JAVA (0) | 2024.09.29 |