백준 14500번: 테트로미노

 

가장 처음에 든 생각은

1,1부터 시작해서 n,m 좌표까지 탐색하며 테트로미노를 하나씩 놔보는 것이다.

이 때, 가능한 테트로미노의 경우는 모두 사전에 정의해야한다.

• I-모양 (회전 시 두 가지 형태)
• O-모양 (회전해도 동일)
• T-모양 (회전 시 네 가지 형태)
• S-모양 (회전 시 두 가지 형태)
• Z-모양 (회전 시 두 가지 형태)
• L-모양 및 대칭된 J-모양 (회전 및 대칭 시 여덟 가지 형태)

 그 코드는 아래와 같다.

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

public class Main {
    static int n, m;
    static int[][] grid;
    static int maxSum = 0;

    // 테트로미노의 모든 가능한 형태를 정의
    static int[][][] tetrominoShapes = {
        // 1자 모양 (회전된 경우 포함)
        {{0, 0}, {0, 1}, {0, 2}, {0, 3}},
        {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
        // 정사각형 모양
        {{0, 0}, {0, 1}, {1, 0}, {1, 1}},
        // L자 모양 (회전 및 대칭된 경우 포함)
        {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
        {{0, 0}, {0, 1}, {0, 2}, {1, 0}},
        {{0, 0}, {1, 0}, {2, 0}, {2, -1}},
        {{0, 0}, {0, 1}, {0, 2}, {-1, 2}},
        {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
        {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
        {{0, 0}, {1, 0}, {1, -1}, {2, -1}},
        {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
        // S자 모양 (회전된 경우 포함)
        {{0, 0}, {0, 1}, {1, 1}, {1, 2}},
        {{0, 0}, {1, 0}, {1, -1}, {2, -1}},
        {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
        {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
        // T자 모양 (회전 및 대칭된 경우 포함)
        {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
        {{0, 0}, {1, 0}, {2, 0}, {1, 1}},
        {{0, 0}, {1, 0}, {2, 0}, {1, -1}},
        {{0, 0}, {0, 1}, {-1, 1}, {1, 1}},
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        grid = new int[n][m];

        // 그리드 입력
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 그리드 탐색 (2차원 배열)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // 각 테트로미노 모양을 시도해봄
                for (int[][] shape : tetrominoShapes) { // shape: 정사각형 하나의 좌표
                    int sum = 0;
                    
                    // 테트로미노 숫자 합 구하기
                    for (int k = 0; k < 4; k++) { // 정사각형 4개: 테트로미노 1개
                        int nx = i + shape[k][0];
                        int ny = j + shape[k][1];
                        if (nx >= 0 && ny >= 0 && nx < n && ny < m) { // 테트로미노 유효 범위 검사
                            sum += grid[nx][ny]; // 테트로미노 내 숫자 합
                            maxSum = Math.max(maxSum, sum); // 최대값 검사
                        }
                    }
                }
            }
        }

        bw.write(maxSum + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

예제 테스트 케이스는 모두 통과했는데, 제출해보니 오답이다.

몇번 더 시도해봤지만 계속 오답으로 처리되어서 새로운 방법을 찾아야 헀다.

 

---

 

 

다음으로 찾은 방법은 DFS를 이용해 가능한 테트로미노의 형태를 모두 찾는 것이다.

DFS 4번의 이동으로 거의 대부분의 테트로미노 모양을 찾을 수 있다.

ㅗ, ㅜ, ㅏ, ㅓ 모양은 DFS로 접근이 불가능하기 때문에 따로 정의해야 한다.

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

public class Main {
	static int n, m;
	static int[][] grid;
	static boolean[][] visited;
	static int maxSum = 0;

	// 방향 배열 (상, 하, 좌, 우)
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	// DFS 사용해서 테트로미노의 모든 경우를 탐색
	static void dfs(int x, int y, int depth, int sum) {
		if (depth == 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 && ny >= 0 && nx < n && ny < m && !visited[nx][ny]) {
				visited[nx][ny] = true;
				dfs(nx, ny, depth + 1, sum + grid[nx][ny]);
				visited[nx][ny] = false;
			}
		}
	}

	// 'ㅗ', 'ㅜ', 'ㅓ', 'ㅏ' 모양의 경우를 처리하는 함수
	static void checkSpecialCase(int x, int y) {
		// ㅗ 모양
		if (x >= 0 && y - 1 >= 0 && y + 1 < m && x + 1 < n) {
			int sum = grid[x][y] + grid[x + 1][y] + grid[x][y - 1] + grid[x][y + 1];
			maxSum = Math.max(maxSum, sum);
		}
		// ㅜ 모양
		if (x >= 0 && y - 1 >= 0 && y + 1 < m && x - 1 >= 0) {
			int sum = grid[x][y] + grid[x - 1][y] + grid[x][y - 1] + grid[x][y + 1];
			maxSum = Math.max(maxSum, sum);
		}
		// ㅓ 모양
		if (x - 1 >= 0 && y >= 0 && x + 1 < n && y + 1 < m) {
			int sum = grid[x][y] + grid[x - 1][y] + grid[x + 1][y] + grid[x][y + 1];
			maxSum = Math.max(maxSum, sum);
		}
		// ㅏ 모양
		if (x - 1 >= 0 && y >= 0 && x + 1 < n && y - 1 >= 0) {
			int sum = grid[x][y] + grid[x - 1][y] + grid[x + 1][y] + grid[x][y - 1];
			maxSum = Math.max(maxSum, sum);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

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

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visited[i][j] = true;
				dfs(i, j, 1, grid[i][j]);
				visited[i][j] = false;

				checkSpecialCase(i, j);
			}
		}

		bw.write(maxSum + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}