[백준 14500] 테트로미노 (JAVA)

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

14500번: 테트로미노

 

 

이문제는 이전에 모든 도형을 정의해놓고 테트리스를 만들어본 경험이 있어 그렇게 풀까 했는데

DFS를 공부한 사람의 입장으로서 문제를 보니 백트래킹으로 간단히 해결이 될듯한 문제였다. 

 

조금 신경써 주어야할 부분이 있다면 

 

 

https://ko.wikipedia.org/wiki/%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8

테트로미노 - 위키백과, 우리 모두의 백과사전

 

위 링크에 있는 테트로미노 도형중 T 형 모양에 해당하는 도형이다.

 

T형 도형은 DFS로는 구현할수없는 도형이므로 별도의 장치를 해주어야 한다.

 

DFS 탐색 진행중 두번째 재귀로 넘어가면 이전 칸에서 다시 탐색할수 있는 부분만 만들어 주면 되는것이다.

 

그럼 코드로 한번 구현을 해보도록 하겠다.

 

먼저 상하좌우 즉 깊이 4인 DFS를 진행할 것 이므로 dx,dy 배열을 선언해주고

방문배열 그리고 행렬값을 입력받을 배열 그리고 행렬의 가로세로, 최대값을 입력받을 변수를 선언해준다.

 

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

 

 

각 배열에 대해 초기화해줄 메소드도 하나 만들어준다.

 

	static void clear() {
		visit = new boolean[n][m];
		metrix = new int[n][m];
	}

 

 

이제 DFS 탐색이다

이 메소드는 재귀 호출시 깊이를 1씩 증가시켜 인자로 주고, 현재칸에 해당하는 숫자도 총합에 더해 인자로 넘겨줄것이다.

 

깊이가 4인 깊이 우선 탐색후 리턴 해주어야 하므로 0부터 시작하는 depth가 3이 되는순간 

최대값을 갱신후 리턴할수 있도록 해주었다.

 

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

	}

 

이제 재귀호출이 가능한 시점을 만들어주면 된다.

 

먼저 이전에 선언한 dx,dy 배열을 통해 반복문을 순회하며 현재칸에서 이동가능한 상하좌우 좌표중

방문하지 않은 좌표로 방문처리후, 재귀 호출, 방문처리 초기화의 과정을 진행해주면 된다.

 

단 이때 위에서 언급한 T형 모양에 대해 별도의 처리인 두번째 재귀 호출에 한해서

이전 좌표에서 한번 더 재귀호출할수 있도록 만들어 주었다.

 

	static void dfs(int x, int y, int depth, int sum) {
		if(depth == 3) {
			max = Math.max(max,sum);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int nowX = x + dx[i];
			int nowY = y + dy[i];
			if(nowX >= 0 && nowY >= 0 && nowX < n && nowY < m && !visit[nowX][nowY]) {
				if(depth == 1) { // ㅗ , ㅜ , ㅏ , ㅓ
					visit[nowX][nowY] = true;
					dfs(x,y,depth + 1,sum + metrix[nowX][nowY]);
					visit[nowX][nowY] = false;
				}
				visit[nowX][nowY] = true;
				dfs(nowX,nowY,depth + 1,sum + metrix[nowX][nowY]);
				visit[nowX][nowY] = false;
			}
		}
	}

 

 

이때 백트래킹을 조금 더 빠르게 하기 위한 장치로,

행렬을 입력받을때 받은 최대값 * 남은 칸수 + 현재까지 칸수의 합이

지금 것 갱신된 전체합의 최대값 보다 작은 경우 바로 리턴해주도록 만들어 주었다.

 

		if(max > sum + maxVal * (4 - depth)) return;

 

 

 

그리고 반복문을 통해 DFS 메소드를 호출해주면 쉽게 답을 얻을 수 있다.

 

	static int pro() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				visit[i][j] = true;
				dfs(i,j,0,metrix[i][j]);
				visit[i][j] = false;
			}
		}
		return max;
	}

 

 

 

주어진 예제중 T 형 모양의 답을 갖는 예제를 실행시켜보면

 

 

 

예상한 답을 내는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj14500 {
	
	static int[] dx = { 1 , 0 , 0 , -1 };
	static int[] dy = { 0 , 1 , -1 , 0 };
	
	static boolean[][] visit;
	
	static int[][] metrix;
	
	static int n,m,max,maxVal;
	
	static void clear() {
		visit = new boolean[n][m];
		metrix = new int[n][m];
	}
	
	static void dfs(int x, int y, int depth, int sum) {
		if(depth == 3) {
			max = Math.max(max,sum);
			return;
		}
		if(max > sum + maxVal * (4 - depth)) return;
		
		for(int i = 0; i < 4; i++) {
			int nowX = x + dx[i];
			int nowY = y + dy[i];
			if(nowX >= 0 && nowY >= 0 && nowX < n && nowY < m && !visit[nowX][nowY]) {
				if(depth == 1) { // ㅗ , ㅜ , ㅏ , ㅓ
					visit[nowX][nowY] = true;
					dfs(x,y,depth + 1,sum + metrix[nowX][nowY]);
					visit[nowX][nowY] = false;
				}
				visit[nowX][nowY] = true;
				dfs(nowX,nowY,depth + 1,sum + metrix[nowX][nowY]);
				visit[nowX][nowY] = false;
			}
		}
	}
	
	
	static int pro() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				visit[i][j] = true;
				dfs(i,j,0,metrix[i][j]);
				visit[i][j] = false;
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		clear();
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j = 0; j < m; j++) {
				metrix[i][j] = Integer.parseInt(st.nextToken());
				maxVal = Math.max(maxVal, metrix[i][j]);
			}
		}
		
		in.close();
		
		System.out.print(pro());
	}

}