백준 / 14500 / 테트로미노

문제

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

입출력 예

해결

'ㅜ'를 제외한 블록들은 dfs로 한 번에 탐색할 수 있다.

오른쪽을 탐색한다고 예를 들었을 때, 4가지 경우의 수로 'ㅜ'를 제외한 블록들을 표현한다. 즉, 깊이 4만큼만 탐색하면 자연스럽게 전부 해당이 된다는 것을 의미한다. 함수명은 dfs()로 하겠다.

 

'ㅜ'는 십자가 모양에서 하나를 빼면 된다. 이 4가지 경우 중에서 가장 큰 값을 찾으면 된다. 이런 패턴을 찾는 함수를 exception() 이라고 하겠다.

 

dfs 방식으로 진행하나 경우의 수를 분리해서 독립적으로 구현이 가능한지를 물어보는 문제이다.

코드

	import java.util.*;
	public class tetris {
	public static int n, m, max = 0;
	public static int[][] arr;
	public static boolean[][] check;
	public static int[] dx = {0, 0, 1, -1};
	public static int[] dy = {1, -1, 0, 0};
	public static void dfs(int x, int y, int depth, int sum) {
	if(depth == 4) {
	max = Math.max(max, sum);
	return;
	}
	for(int i = 0 ; i < 4 ; i++) {
	int ax = x + dx[i];
	int ay = y + dy[i];
	if(ax >= 0 && ay >= 0 && ax < n && ay < m && check[ax][ay] == false) {
	check[ax][ay] = true;
	dfs(ax, ay, depth + 1, sum + arr[ax][ay]);
	check[ax][ay] = false;
	}
	}
	}
	public static void exception(int x, int y) {
	// 상하좌우 이동
	for(int i = 0 ; i < 4 ; i++) {
	int total = arr[x][y];
	boolean flag = true;
	// 십자가에서 하나 뺀거니까 3번만 이동
	for(int j = 0 ; j < 3 ; j++) {
	int ax = x + dx[(i + j) % 4];
	int ay = y + dy[(i + j) % 4];
	if(ax >= 0 && ay >= 0 && ax < n && ay < m) {
	total += arr[ax][ay];
	} else {
	flag = false;
	break;
	}
	}
	if(flag) max = Math.max(max, total);
	}
	}
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	m = sc.nextInt();
	arr = new int[n][m];
	check = new boolean[n][m];
	for(int i = 0 ; i < n ; i++)
	for(int j = 0 ; j < m ; j++)
	arr[i][j] = sc.nextInt();
	for(int i = 0 ; i < n ; i++)
	for(int j = 0 ; j < m ; j++) {
	check[i][j] = true;
	dfs(i, j, 1, arr[i][j]);
	exception(i, j);
	check[i][j] = false;
	}
	System.out.println(max);
	return;
	}
	}

view raw ex.java hosted with ❤ by GitHub

 

느낀점

처음 테트리스 모양을 보고 대칭, 이동, 회전을 해야한다는 생각에 막막했었는데 솔루션을 보니 무릎을 쳤다. 왜 저런 생각을 못했을까..? 아무 도움 없이 이런 문제의 해답을 찾으려면 얼마나 더 해야할까..ㅠㅠ 더 열심히 해야겠다.

 

출처

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

14500번: 테트로미노

https://hyeooona825.tistory.com/60

[백준 14500] 테트로미노