[Java] 백준 BOJ / 14500번: 테트로미노

테트로미노

문제

---

문제 설명

숫자가 적혀진 N X M 크기의 종이가 있을 때 그 위에 주어진 4칸짜리 도형들 중 하나를 적절하게 배치해서 가장 최대의 값을 구하는 문제이다.

문제에서 주어진 모형들을 잘 살펴보면 보라색 ㅜ 모양 을 제외하고는 모두 상하좌우 완전탐색을 하면 전부 확인할 수 있다.

보라색 모양을 완전 탐색하기 위해서는 세 면을 공유하고 있는 가운데 블럭을 기준으로 탐색을 해주어야 이 모양까지 커버할 수 있기 때문에 이 조건을 고려해서 문제를 풀어야 한다.

---

구현

일단 각각의 칸에서 모든 가능한 모양을 확인해 봐야 하기 때문에 DFS로 구현한다.

모든 정점에서 해당 칸을 방문했다고 확인한 후에 DFS를 돌고 빠져나오면 해당칸의 방문여부를 false로 처리한다.

즉 모든 정점에서 DFS를 시작하고, 백트래킹으로 되돌아오는 것이다.

//DFS 시작
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		visited[i][j] = true;
		dfs(i, j, arr[i][j], 1);
		visited[i][j] = false;
	}
}

DFS 함수에서는 현재 위치의 row, col, 현재까지의 합이 저장되어있는 sum, 그리고 몇개 탐색했는지 저장하는 변수인 count를 인자로 한다.

만약에 count 가 4라면 4칸인 경우를 탐색한 거니깐 max 변수를 초기화한다.

//조각이 완성된 경우
if (count == 4) {
	max = Math.max(max, sum);
	return;
}

그 후 dx 배열과 dy 배열을 사용하여 범위에 벗어나지 않고 방문하지 않은 다음 좌표를 찾는다.

만약에 현재까지 탐색한 블럭이 2개인 경우를 여기서 생각해주어야 한다.

2개인 경우에서 보라색 ㅜ 모양을 탐색할 경우를 알려주어야 한다.

ㅜ 모양을 탐색하려면 중앙에 위치한 곳의 좌표에서 다시 한 번 DFS를 돌려주어야 한다.

한 방향으로만 4칸을 이동하는 DFS로는 만들 수 없는 ㅗ, ㅜ, ㅓ, ㅏ 모양을 처리하기 위한 로직이다.

if (count == 2) {
	visited[nx][ny] = true;
	dfs(row, col, sum + arr[nx][ny], count + 1);
	visited[nx][ny] = false;
}

이렇게 예외처리를 하고 아래에서는 다음 좌표로 가야하기 때문에 DFS에 다음 좌표인 nx와 ny를 넣고 돌려주면 된다.

---

코드

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

public class Main_14500 {
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int max;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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());

        arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //DFS 시작
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                dfs(i, j, arr[i][j], 1);
                visited[i][j] = false;
            }
        }

        System.out.println(max);
    }

    static void dfs(int row, int col, int sum, int count) {
        //조각이 완성된 경우
        if (count == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = row + dx[i];
            int ny = col + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            if (!visited[nx][ny]) {
                if (count == 2) {
                    visited[nx][ny] = true;
                    dfs(row, col, sum + arr[nx][ny], count + 1);
                    visited[nx][ny] = false;
                }

                visited[nx][ny] = true;
                dfs(nx, ny, sum + arr[nx][ny], count + 1);
                visited[nx][ny] = false;
            }
        }
    }
}