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

 

풀이

키워드

• 브루트포스
• DFS

  N과 M의 크기가 크지 않고, 이것 저것 다양하게 시도해보아야 해서 브루트포스로 풀어야 한다는 것을 알 수 있다.

문제에 나온 그대로 푼다면 DFS 함수를 정의하여 각 위치를 입력받은 뒤, 도형 모양대로 값을 계산해보면 된다. 그러나 이렇게 할 경우, 중복되는 경우의 수가 많이 생기고, 코드가 너무 길어질 것 같았다. 

  그래서 DFS로 한점 한점 탐색하며 탐색한 크기가 4가 되는 경우 현재까지의 값을 max와 비교하여 최대의 크기를 찾는 방법을 사용했다. 다만, 이 경우에도 중복이 생길 수 있으므로 DFS함수 안에서 다음 위치로 뻗어 나갈 때, 위로는 뻗어나가지 않도록 설정했다.

  즉 빨간색 점에서 위로는 못 가고, 초록색 부분으로만 뻗어나갈 수 있는 것이다. 이렇게 해도 여전히 좌, 우로는 중복이 생길 수 있지만, 위 아래로는 중복이 생기지 않는다. 좌, 우 중복을 없애고자 왼쪽으로 가는 방향도 없애자고 할 수도 있다. 그러나 그렇게 할 경우

  이 같은 도형을 표현할 수 없다. 즉 맨 위에서 시작할 경우 아래에서 내려오다가 왼쪽으로 꺾을 수 없고, 맨 왼쪽에서 시작할 경우 맨 위로 방향을 꺾을 수 없다. 따라서 좌, 우 중복은 어쩔 수 없이 허용했다.

 

  주의할 점이 하나 더 있다.

  1번에서 시작해서 2번까지 내려온 경우, 다음으로 갈 수 있는 방향은 파, 초, 주 세 방향이다. 그러나 일반적인 DFS에서는 두 방향을 동시에 방문하는 것은 불가능하다. 그러나 테트로미노에서는 'ㅗ' 와 같은 모형이 존재한다. 따라서 이를 표현해 주기 위해 현재까지 방문한 노드 개수가 2일 경우 한번에 두 개의 노드를 방문하여 'ㅗ' 모양의 값을 최댓값과 비교해볼 수 있도록 예외로 설정해줬다.

---

코드

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

public class Main {
	static int N, M;
	static int [][] arr;
	static int [] dy = {0, 1, 0};
	static int [] dx = {1, 0, -1};
	static int max = 0;
	static boolean [][] visited;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = 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++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				bf(i, j, 1, 0);
			}
		}
        
		System.out.print(max);
	}
	
	public static void bf(int y, int x, int n, int value) {
		value += arr[y][x];
        
		if (n == 4) {
			max = Math.max(value, max);
			return;
		}
		
		visited[y][x] = true;
		
		for(int i = 0; i < 3; i++) {
			int nextY = y + dy[i];
			int nextX = x + dx[i];
			if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
				continue;
			if (visited[nextY][nextX]) {
				continue;
			}
			bf(nextY, nextX, n+1, value);
		}
		
		// 'ㅗ' 모양 예외처리
		if (n == 2) {
			for (int i = 0; i < 3; i++) {
				int nextY1 = y + dy[i];
				int nextX1 = x + dx[i];
				int nextY2 = y + dy[(i+1)%3];
				int nextX2 = x + dx[(i+1)%3];
				
				if (nextY1 < 0 || nextY1 >= N || nextX1 < 0 || nextX1 >= M)
					continue;
				if (nextY2 < 0 || nextY2 >= N || nextX2 < 0 || nextX2 >= M)
					continue;
				if (visited[nextY1][nextX1] || visited[nextY2][nextX2]) {
					continue;
				}
				max = Math.max(max, value + arr[nextY1][nextX1] + arr[nextY2][nextX2]);
			}
		}
		visited[y][x] = false;
	}
}

출처 : www.acmicpc.net/problem/14500

14500번: 테트로미노