[백준] 14500 테트로미노 - Implementation / Java

• 문제 링크

14500번: 테트로미노

 

• 풀이 과정

문제에 제시된 5가지의 테트로미노 중 'ㅜ' 를 제외한 나머지 테트로미노들은 일반적인 dfs로 완전탐색하여 구현 가능하나,

ㅜ의 경우 위와 같이 탐색의 깊이가 2인 칸, 즉 테트로미노가 두 방향으로 분기되는 칸에서 분기를 준다.

3번째 탐색 위치를 현재 위치에서 재탐색하여 해당 테트로미노를 구현한다.

 

이렇게 모든 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값이 max 변수에 갱신되어 정답이 출력된다.

 

• 풀이 코드

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

public class Main {

	static int n, m, max;
	static int[][] arr;
	static boolean[][] visit;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

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

		visit = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visit[i][j] = true;
				dfs(i, j, 1, arr[i][j]);
				visit[i][j] = false;
			}
		}

		bw.write(max + "\n");
		bw.flush();
	}

	private static void dfs(int y, int x, int depth, int sum) {
		if (depth == 4) {
			max = Math.max(max, sum);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;

			if (!visit[ny][nx]) {
				if (depth == 2) {
					visit[ny][nx] = true;
					dfs(y, x, depth + 1, sum + arr[ny][nx]);
					visit[ny][nx] = false;
				}

				visit[ny][nx] = true;
				dfs(ny, nx, depth + 1, sum + arr[ny][nx]);
				visit[ny][nx] = false;
			}
		}
	}

}