14500 테트로미노

 

 

풀이

 

다른 사람의 블로그를 참고했다.

 

N*M 개의 각점에 대해서 테트로미노를 모두 적용해보며 최대의 합을 구하기는 불편하다.

 

다른 방법으로 dfs를 이용할 수 있다.

 

테트로미노는 정사각형 4개를 이어 붙인 폴리오미노이기 때문에,

한 점 (i,j)에서 depth == 4를 만족할때까지 dfs를 적용하고, 그때 dfs가 적용되는 각 칸의 값들을 더해나가며 최댓값을 구한다.

 

 

예를 들어서 (0,0) 의 위치에서 depth=4 를 만족하는 dfs를 진행하면, 아래와 같이 테트로미노가 완성된다.

 

 

테트로미노를 회전, 대칭 시켜도 된다고 했는데,

depth==4 를 만족할 때까지 dfs를 진행시키면, 위의 테트로미노가 회전, 대칭되는 경우도 알아서 해결된다.

 

그런데, 문제는 ㅜ 모양이다.

 

이런식으로, 한번 왔던 점인, (0,1) 을 다시 한 번 방문해야 한다.

그래서 이 경우는, dfs가 아니라 따로 solve 메소드를 만들어서 해결했다.

 

말 그대로 (0,0), (0,1), (0,2), (1,1) 위치의 값을 더해주면서 최댓값을 구하는 것이다.

 

ㅜ, ㅏ, ㅗ, ㅓ 회전, 대칭시키면서 최댓값을 구한다.

 

 

 

최종 코드

 

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

public class Main {

	static int map[][];
	static boolean visit[][];
	static int max;
	static int N;
	static int M;
	
	
	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());
		
		visit = new boolean[N][M];
		map = new int[N][M];
		
		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());
			}
		}
		
		
		max = 0;
		
		for(int i=0; i<N;i++) {
			for(int j=0; j<M;j++) {
				visit[i][j] = true;
				dfs(i,j,map[i][j], 1);
				visit[i][j] = false;
				solve(i,j);
			}
		}
		
		
		System.out.println(max);
		
		
	}
	
	
	
	public static void dfs(int x, int y, int sum, int depth) {
		
		
		if(depth==4) {
			max = Math.max(max, sum);
			return;
		}

		
		int dx [] = {-1,1,0,0};
		int dy [] = {0,0,-1,1};
		
		
		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) {
				if(!visit[nx][ny]) {
				visit[nx][ny] = true;
				dfs(nx, ny, sum+map[nx][ny], depth+1);
				visit[nx][ny] = false;
				
				}
		  }
		}
	}
	
	
	public static void solve(int x, int y) {
		
		if(x<=N-2 && y<=M-3) {
			max = Math.max(max, map[x][y] + map[x][y+1] + map[x][y+2] + map[x+1][y+1]);
		}
		
		
		if(x>=1 && y<=M-3 ) {
			max = Math.max(max, map[x][y] +map[x][y+1] + map[x][y+2] + map[x-1][y+1]);
			
		}
		
		
		if(x<=N-3 && y<=M-2) {
			max = Math.max(max, map[x][y] + map[x+1][y]+map[x+2][y]+ map[x+1][y+1]);
		}
		

		if(x<=N-3 && y>=1 ) {
			max = Math.max(max, map[x][y] + map[x+1][y] + map[x+2][y]+map[x+1][y-1]);
		}
		
	}
}

 

 

참고 블로그 : 

https://girawhale.tistory.com/35

[백준] 14500번: 테트로미노 - JAVA