[백준] 14500번 - 테트로미노

알고리즘/백준

[백준] 14500번 - 테트로미노

땀두 2022. 3. 23. 08:23

백트래킹을 이용한 문제이다. 문제에 사용되는 테트로미노를 만드는 것 자체가 어려웠던 것 같다. 이 부분에서 백트래킹을 이용하여 첫 탐색부터 depth가 4가 되는 지점까지 탐색을 하도록 하여 모양을 만들었다. 하지만 여기서 ㅁ모양이나 L, l, N과 같은 모양은 만들 수 있지만 ㅏ, ㅓ, ㅗ, ㅜ 와 같은 한 붓 그리기가 불가능 한 모양들은 만들 수 없기 때문에 이 부분에 대해서는 또 다른 함수를 만들어 탐색하였다.

처음 문제 풀이에 있어서는 ㅏ, ㅓ, ㅗ, ㅜ 부분이 4개이기 때문에 분기처리하여 처리해주었지만 종종 조언을 구하는 케로츄님(https://blog.naver.com/kerochuu)의 첨언을 통해 이 부분에 대해서 + 모양을 구현 후, 필요 없는 한 개의 부분을 제거하는 식의 방식으로도 문제를 해결해보았다.

package algorithm.class3;

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

public class p14500 {
	public static int[] nx = { -1, 0, 0, 1 };
	public static int[] ny = { 0, -1, 1, 0 };
	public static boolean[][] visited;
	public static int[][] ary;
	public static int a;
	public static int b;
	public static int rst = 0;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		ary = new int[a][b];
		visited = new boolean[a][b];

		for (int i = 0; i < a; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < b; j++) {
				ary[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				visited[i][j] = true;
				dfs(i, j, 0, 0);
				visited[i][j] = false;
				plus(i, j);
			}
		}
		System.out.println(rst);
	}

	public static void dfs(int x, int y, int depth, int cnt) {
		if (depth == 4) {
			rst = Math.max(cnt, rst);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int X = x + nx[i];
			int Y = y + ny[i];

			if (X >= 0 && Y >= 0 && X < a && Y < b) {
				if (visited[X][Y] == false) {
					visited[X][Y] = true;
					dfs(X, Y, depth + 1, cnt + ary[X][Y]);
					visited[X][Y] = false;
				}
			}
		}
	}

	public static void otherCase(int x, int y) {
		if (x + 2 < a && y + 1 < b && x >= 0 && y >= 0) {// ㅏ
			rst = Math.max(rst, ary[x][y] + ary[x + 1][y] + ary[x + 1][y + 1] + ary[x + 2][y]);
		}

		if (x + 2 < a && y - 1 >= 0 && x >= 0 && y < b) {// ㅓ
			rst = Math.max(rst, ary[x][y] + ary[x + 1][y] + ary[x + 1][y - 1] + ary[x + 2][y]);
		}

		if (x - 1 >= 0 && y + 2 < b && x < a && y >= 0) {// ㅗ
			rst = Math.max(rst, ary[x][y] + ary[x][y + 1] + ary[x - 1][y + 1] + ary[x][y + 2]);
		}

		if (x + 1 < a && y + 2 < b && x >= 0 && y >= 0) {// ㅜ
			rst = Math.max(rst, ary[x][y] + ary[x][y + 1] + ary[x + 1][y + 1] + ary[x][y + 2]);
		}
	}

	public static void plus(int x, int y) {
		int sum = ary[x][y];
		int min = Integer.MAX_VALUE;
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			int X = x + nx[i];
			int Y = y + ny[i];

			if (X >= 0 && Y >= 0 && X < a && Y < b) {
				min = Math.min(min, ary[X][Y]);
				sum += ary[X][Y];
				cnt++;
			}
		}
		if (cnt >= 3) {
			if (cnt == 4) {
				sum -= min;
			}
			rst = Math.max(rst, sum);
		} else {
			return;
		}
	}
}

이 문제에서는 답안이 틀릴 경우에 반례 찾기가 까다로웠는데 백준 게시판에 있는 https://www.acmicpc.net/board/view/61597 반례를 통해서 어떠한 케이스에서 오류가 발생하였는지 찾기 용이하였다.

반례 - 모두 값이 10이 나와야 정상적인 답안이다.

저작자표시 비영리 동일조건 (새창열림)