백준 14500번: 테트로미노

문제

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

---

풀이

폴리오미노란 크기가 1×1인 정사각형을 다음과 같은 조건을 만족하면서 여러 개 이어서 붙인 도형입니다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라고 할 때 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합의 최대값을 구하는 문제입니다.

---

접근

처음에 이 문제를 보고 알고리즘 분류가 브루트포스로 돼있어서 만들 수 있는 테트로미노 5개의 모양 그대로 5번 for문을 반복하려고 했는데 너무 노가다같다는 생각이 들었습니다. 그래서 방법을 생각하다가 dfs 메소드가 생각났습니다. 정사각형을 4개만 이어붙이면 되기 때문에 깊이가 4보다 작을 때만 실행하면 될 것 같았습니다. 하지만 문제가 있었는데 일반적인 방법으로 ㅓㅜㅏㅗ 와 같은 모양을 만들 수 없었습니다. 그래서 이와 같은 모양을 만들기 위해 mountain 메소드를 추가로 만들었습니다. mountain 메소드 관련 설명을 아래에 적어두겠습니다.

---

코드

자바

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

public class Main {

    static final int[] dx = { -1, 0, 1, 0 };
    static final int[] dy = { 0, -1, 0, 1 };

    static int n, m, max = 0;
    static int[][] tetromino;
    static boolean[][] visited;

    public static void dfs(int x, int y, int dpth, int sum) {
        if (dpth == 4) { // (2)
            max = Math.max(max, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny]) { // (1)
                visited[nx][ny] = true;
                dfs(nx, ny, dpth + 1, sum + tetromino[nx][ny]);
                visited[nx][ny] = false;
            }
        }
    }

    public static void mountain(int x, int y) {
        int wing = 4, min = Integer.MAX_VALUE;
        int sum = tetromino[x][y];
        for (int i = 0; i < 4; i++) {
            if (wing < 3) return; // (4)
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < m && 0 <= ny && ny < n) { // (3)
                min = Math.min(min, tetromino[nx][ny]);
                sum += tetromino[nx][ny];
            } else wing--;
        }
        if (wing == 4) { // (5)
            sum -= min;
        }
        max = Math.max(max, sum);
    }

    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());
        tetromino = new int[m][n];
        visited = new boolean[m][n];
        for (int j = 0; j < n; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < m; i++) {
                tetromino[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                visited[i][j] = true;
                dfs(i, j, 1, tetromino[i][j]);
                mountain(i, j);
                visited[i][j] = false;
            }
        }
        System.out.println(max);
    }
}

모든 입력이 끝나면 2중 for문을 이용하여 모든 점(i, j)에서 (i, j)의 방문처리를 해준 뒤에 dfs(i, j, 1, tetromino[i][j])을 실행합니다.

 

(1) 다음으로 이동할 좌표(nx, ny)가 이동 가능한 좌표인지, 방문한 적이 없는지 확인합니다.

위의 조건을 만족한다면 visited[nx][ny]를 true로 초기화해준 뒤에 dfs(nx, ny, dpth + 1, sum + tetromino[nx][ny])를 재귀적으로 실행하고 다시 visited[nx][ny]를 false로 초기화해줍니다.

 

(2) dpth가 4라면 테트로미노가 완성된 것입니다.

테트로미노 안의 합의 최대값인 max와 만들어진 테트로미노 안의 합인 sum을 비교하여 max를 구한 후에 return합니다.

 

dfs 메소드가 종료되면 mountain(i, j)를 실행하고 visited[i][j]를 false로 초기화합니다.

mountain(int x, int y) 메소드는 현재 위치(x, y)에서 4방향으로((+) 모양으로) 날개를 만듭니다. 4개의 날개중에 가장 작은 값을 버리면 ㅗㅜㅏㅓ 모양이 만들어지는 방식입니다. mountain 메소드 안에 wing은 날개의 개수를, min은 4개의 날개중에 가장 작은 값을 의미하며 sum은 만들어질 테트로미노 안의 합을 의미합니다.

 

(3) 다음으로 이동할 좌표(nx, ny)가 이동 가능한 좌표인지 확인합니다.

이동 가능하다면 min 값을 비교하여 초기화하고 sum에 tetromino[nx][ny]값을 더해줍니다.

이동이 불가능하다면 wing에서 1을 빼줍니다.

 

(4) wing이 3보다 작다면 메소드를 종료합니다.

만들고자하는 테트로미노의 날개의 개수는 3개입니다. 하지만 (3)번 과정을 거치면서 wing이 3개보다 작아진다면 테트로미노를 만들 수 없기 때문에 return하여 메소드를 종료합니다.

 

(5) wing == 4인지 확인합니다.

날개가 4개라면 4개의 날개중에 가장 작은 값을 가지는 날개 1개를 버려야합니다. (3)번 과정을 거치면서 min이 구해졌기 때문에 sum에서 min을 빼줍니다. 이후 max와 sum을 비교하여 max를 구한 후에 return합니다.

 

모든 과정을 종료한 후에 max를 출력합니다.

C언어

#include <stdio.h>
#define math_max(a, b) a > b ? a : b
#define math_min(a, b) a < b ? a : b
int n, m, max = 0, **tetromino, **visited;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
void dfs(int x, int y, int dpth, int sum) {
	if (dpth == 4) {
		max = math_max(max, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny]) {
			visited[nx][ny] = 1;
			dfs(nx, ny, dpth + 1, sum + tetromino[nx][ny]);
			visited[nx][ny] = 0;
		}
	}
}
void mountaion(int x, int y) {
	int wing = 4, min = 1001;
	int sum = tetromino[x][y];
	for (int i = 0; i < 4; i++) {
		if (wing < 3) return;
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < m && 0 <= ny && ny < n) {
			min = math_min(min, tetromino[nx][ny]);
			sum += tetromino[nx][ny];
		}
		else wing--;
	}
	if (wing == 4) sum -= min;
	max = math_max(max, sum);
}
main() {
	scanf("%d %d", &n, &m);
	tetromino = (int**)malloc(sizeof(int*) * m);
	visited = (int**)malloc(sizeof(int*) * m);
	for (int i = 0; i < m; i++) {
		tetromino[i] = (int*)malloc(sizeof(int) * n);
		visited[i] = (int*)malloc(sizeof(int) * n);
		for (int j = 0; j < n; j++) {
			visited[i][j] = 0;
		}
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < m; i++) {
			scanf("%d", &tetromino[i][j]);
		}
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < m; i++) {
			visited[i][j] = 1;
			dfs(i, j, 1, tetromino[i][j]);
			mountaion(i, j);
			visited[i][j] = 0;
		}
	}
	printf("%d", max);
}

자바를 이용한 풀이와 동일합니다.

 

---

결론

이 문제를 풀고난 후에 다른 사람들이 푼 풀이를 읽어봤습니다. 다른 사람들은 mountain 메소드와 같은 별개의 함수를 만들지 않고 dfs 메소드 안에서 ㅗㅓㅜㅏ와 같은 모양의 테트로미노를 만들었는데 이 코드는 시간이 날 때 꼭 이해해보고 싶다는 생각이 들었습니다.