[BAEKJOON_14500 - JAVA] 테트로미노

문제

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

14500번: 테트로미노

 

 

과정

문제 이해에 시간이 걸린 문제

1. 문제 조건을 활용 'ㅗ' 제외 모든 도형이 DFS를 통해 탐색 가능.
2. DFS를 통해 'ㅗ' 모양을 제외한 모든 도형에 대한 탐색.
3. DFS를 활용하지 못하는 'ㅗ' 도형을 탐색.
4. 1,2번의 탐색 결과값을 최댓값과 비교 및 갱신.

 

 

풀이

• DFS 통해 기저조건으로 depth == 4 일때 정지한다면, 테트로미노의 도형과 같은것을 이해.
  (해당 문제에 대칭, 회전이 가능하다는 문장이 중요.)
• 'ㅗ' 도형에 대해서는 별도로 메소드 관리.
  (유효 범위 주의)
• 위의 두메소드 수행마다 max 값 비교 및 갱신.

 

 

문제해결

'ㅗ' 모형에 대해서는 DFS가 불가능했으며, 처음에는 대칭 및 회전에 대해 하드코딩.
이후, 검색을 통해 좋은 코드를 참고하여 재작성.
( '+' 모양을 기준으로 가장 작은 날개 부분을 제외하는 방법.  4개의 날개중 하나를 제거 한다면 'ㅗ' 모양이 된다.)
→ '+' 모양에서 최소값 한개를 없애는 방법을 생각하는 시야 필요

 

 

알고리즘 지식

• 브루트 포스 (DFS)

 

 

JAVA코드

/*
 * 대칭 회전 가능 -> DFS 사용 가능.
 * ㅗ 모양의 경우 DFS 사용 불가능.
 * 
 * 1. map의 모든 구간에 대해 4 크기의 테트로미노를 만드는 DFS를 돌린다.
 * 2. 테트로미노의 최댓값을 계산하면 갱신한다.  
 * 
 */

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[][] map;
	static boolean[][] visited;
	static int[] dy = { -1, 1, 0, 0 }; // 상 하 좌 우
	static int[] dx = { 0, 0, -1, 1 };

	// 범위 검사
	public static boolean isValid(int row, int col) {
		if (row < 0 || row >= N || col < 0 || col >= M)
			return false;
		return true;
	}

	public static void tetromino() {
		// map 전체 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				dfs(i, j, 0, 0);
				exception(i, j);
			}
		}
	}

	// ㅗ 모양 제외 모양들 구현
	private static int dfs(int row, int col, int depth, int sum) {

		if (depth == 4) {
			max = Math.max(max, sum);
			return 0;
		}

		for (int k = 0; k < 4; k++) {
			int nextRow = row + dy[k];
			int nextCol = col + dx[k];

			if (isValid(nextRow, nextCol) && !visited[nextRow][nextCol]) {
				visited[nextRow][nextCol] = true;
				dfs(nextRow, nextCol, depth + 1, sum + map[nextRow][nextCol]);
				visited[nextRow][nextCol] = false;

			}
		}

		return sum;
	}

	// ㅗ 모양 구현
	private static void exception(int row, int col) {
		int wing = 4; // 가운데에서의 상하좌우 날개
		int min = Integer.MAX_VALUE;
		int sum = map[row][col];
		for (int i = 0; i < 4; i++) {
			int nextRow = row + dx[i];
			int nextCol = col + dy[i];

			// 날개가 2개이상 없다면 ㅗ 모양이 아니다. 그러므로 함수를 종료한다.
			if (wing <= 2)
				return;
			// 날개가 맵 바깥에 있는 경우
			if (!isValid(nextRow, nextCol)) {
				wing--;
				continue;
			}
			min = Math.min(min, map[nextRow][nextCol]);
			sum = sum + map[nextRow][nextCol];
		}
		// 날개가 4개일때 가장 작은 날개를 없애야 ㅗ,ㅏ,ㅓ,ㅜ 모양이 나온다.
		if (wing == 4) {
			sum = sum - min;
		}
		max = Math.max(max, sum);
	}

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 행
		M = Integer.parseInt(st.nextToken()); // 열
		map = new int[N][M]; // 입력받을 맵
		visited = new boolean[N][M]; // 방문 체크
		max = 0; // 최댓값

		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());
			}
		} // end of input

		tetromino();

		System.out.println(max);
		br.close();
	}
}