[백준] 14500. 테트로미노 (구현/Java)

[백준] 14500. 테트로미노

 

📌 풀이 과정

정사각형 4개를 이어 붙인 1X1 정사각형은 테트로미노라고 하며, 다음과 같은 5가지가 있다.

각 지점마다 만들 수 있는 도형을 탐색하면 된다.
사실 처음에는 테트로미노를 회전/대칭한 형태를 하드코딩 해야하나.. 싶었다.

1. 다섯가지 중에서 ㅜ 모양을 제외한 나머지는 depth가 4인 dfs로 탐색

노란색 칸 : 탐색의 시작 칸
노란색 칸에서 시작해서 dfs로 탐색하는 것이다.
탐색하는 지점은 visited 처리를 해주고, dfs 탐색 후 visited를 다시 원복시켜야 한다.

 

2. ㅜ 모양은 ㅓ, ㅏ, ㅗ로 가능하므로 인접한 4칸 중 3칸을 선택한다. (조합)

 

✨ 제출 코드

메모리: 35384 KB

시간: 588 ms

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

public class Main {

	static int N, M, max;
	static int[][] paper;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		max = Integer.MIN_VALUE;
		N = Integer.parseInt(st.nextToken()); // 세로 크기
		M = Integer.parseInt(st.nextToken()); // 가로 크기
		paper = 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++) {
				paper[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, paper[i][j]);
				visited[i][j] = false;
				
				combi(i, j, 0, 0, paper[i][j]);
			}
		}
		
		System.out.println(max);
	}
	
	private static void combi(int x, int y, int cnt, int start, int sum) {
		if(cnt == 3) {
			max = Math.max(max, sum);
			return;
		}
		
		for(int i = start; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			combi(x, y, cnt + 1, i + 1, sum + paper[nx][ny]);
		}
	}
	
	private 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 nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue;
			visited[nx][ny] = true;
			dfs(nx, ny, depth + 1, sum + paper[nx][ny]);
			visited[nx][ny] = false;
		}
	}
	
}