[백준 14500] 테트로미노

 이 문제는 4개짜리 테트로미노 블럭을 주어진 이차원 배열에 놨을 때 배열의 값의 합이 최대가 되는 값을 구하는 문제입니다. 폴리오미노의 조건은 아래와 같습니다.

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

이 때, 정사각형 4개를 이어붙인 폴리오미노를 테트로미노라 하고 아래의 그림과 같이 5가지 종류입니다.

 저도 처음에는 '5개를 어떻게 회전하지.. 4*4배열을 생성해서 그 배열을 회전해야하나..' 하는 함정에 빠졌습니다. 이것을 어떻게 해결하냐가 관건입니다.

이 문제는 dfs로 간단하게 풀리는 문제입니다. 'ㅜ' 블럭을 제외한 4개의 블럭은 한번에 그릴 수 있죠? 다시 말하면 dfs로 한번에 탐색할 수 있는 것이죠. 아래의 그림을 보시면 이해되실거예요!

<'ㅜ'블록을 제외한 나머지 블록의 배열 값 합 구하기>

 위의 그림을 예로 들면, 첫 번째 배열에서 아래칸에서 dfs를 시작하겠습니다. 우선 오른쪽을 탐색한다고 생각하면 두번째 그림이 되겠죠? 이후에 2칸을 더 탐색하는 경우는 오른쪽의 4가지 경우입니다. 이 그림은 위의 'ㅜ' 블럭을 제외한 나머지 블럭들을 나타냅니다. 두번째 그림에서 오른쪽을 탐색하지 않고 위, 아래, 왼쪽을 탐색한다면 이 4개의 블럭들을 회전한 그림이 나오겠죠! 따라서 4만큼만 dfs를 돌려서 나오는 배열 값의 합 중 최대값을 MAX변수에 저장하면 됩니다.

<'ㅜ'블록의 배열 값 합 구하기>

 그럼 이제 'ㅜ' 블럭만 남았죠? 'ㅜ' 블럭은 위의 그림과 같이 4가지의 ㅏ, ㅓ, ㅗ, ㅜ 블럭을 구해 MAX값을 갱신했습니다. 이 문제는 'ㅜ'블럭과 나머지 블럭을 나누고 dfs를 적용할 수 있냐가 관건이었습니다! 아래 전체 소스코드를 첨부하겠습니다.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class boj14500 {
	static int N, M, MAX = 0;
	static int[][] map, visited;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -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());
	visited = new int[N][M];
	map = new int[N][M];
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < M; j++) {
	map[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	for (int i = 0; i < N * M; i++) {
	int x = i / M;
	int y = i % M;
	visited[x][y] = 1;
	dfs(x, y, 1, map[x][y]);
	CalculateSpecialBlock(x, y);
	visited[x][y] = 0;
	}
	System.out.println(MAX);
	}
	private static void dfs (int x, int y, int count, int sum) {
	if (count == 4) {
	MAX = Math.max(MAX, sum);
	return;
	}
	for (int i = 0; i < 4; i++) {
	int sx = x + dx[i];
	int sy = y + dy[i];
	if (sx >= 0 && sx < N && sy >= 0 && sy < M && visited[sx][sy] == 0) {
	visited[sx][sy] = 1;
	dfs(sx, sy, count + 1, sum + map[sx][sy]);
	visited[sx][sy] = 0;
	}
	}
	}
	private static void CalculateSpecialBlock (int x, int y) {
	for (int i = 0; i < 4; i++) {
	int total = map[x][y];
	boolean flag = true;
	for (int j = 0; j < 3; j++) {
	int sx = x + dx[(i + j) % 4];
	int sy = y + dy[(i + j) % 4];
	if (sx >= 0 && sx < N && sy >= 0 && sy < M) {
	total += map[sx][sy];
	} else {
	flag = false;
	break;
	}
	}
	if (flag) MAX = Math.max(MAX, total);
	}
	}
	}

view raw boj14500.java hosted with ❤ by GitHub