[백준 - 14500번] 테트로미노 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)

안녕하세요. 이번에는 저번 삼성 SW 역량테스트 문제들에 하나인 테트로미노를 풀어보겠습니다.

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

문제에 대해서 간략하게 설명해보도록 하죠. 

 위의 그림에 있는 블럭들을 n*m자리 숫자가 적힌 판에다가 "1개만" 놓고 그 블럭 아래에 적힌 숫자들의 합이 가장 큰 경우를 따져 주는 문제입니다. 

조건 중에 약간 까다로운 조건이 하나 있는데 바로  회전이나 대칭을 시켜도 된다. 입니다.

이 조건은 결국 우리가 따져야 할 조건이 여러가지가 있다는 사실을 뜻하기도 합니다. 

저는 이문제를 보고 고민을 좀 하게된게 이걸 어떤식으로 계산을 해야할까를 고민을 많이 했죠. 도대체 어떤 경우에 이 합이 최대가 되는 경우를 찾을 수 있을까?

저는 일단 DFS를 기준 삼아서 하면 어떨까 생각했는데, 막상 구현하고 나니까 DFS는 아니고 함수 구현 방식으로 문제를 풀었습니다. 

함수 구현방식이나 DFS의 경우 고민을 많이하게 되는데요. 

가장 좋은 방법은 직접 다 해보는 겁니다.

이상입니다.  (이러면 욕먹겠지만ㅋㅋ)

다 해본다는 것이 진짜로 손으로 직접 다해보는 것이 아니라, "컴퓨터를 굴려서 직접 다 해보게 만들면 된다는 것이죠"

이 문제는 기본적으로 1. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며,

2. 회전이나 대칭을 시켜도 된다. 

두 조건을 잘 상기해야합니다. 1번 조건은 n*m의 사각형 끝에라도 테트로미노가 닿을수도 있다는 뜻이고, 

ex)

숫자 영역이 어떻든간에 블럭하나가  확실하게 끼워질수 있게끔 만들어줘야 한다는 것이죠.  이렇게되면 영역외의 부분을 처리 하기가 상당히 까다롭습니다. 

왜냐하면, 그 부분이 맨끝점일때 경우를 if문으로 일일히 강제해야되고, 심지어 그 경우가 내가 생각하지 못한 경우로 오류가 난경우 코드가 멈추게 되는 단점도 존재합니다. 

이때 저는 가장 간단한 방법으로 이 문제를 해결해봤는데요. 

숫자 영역의 주변부를 "0"으로 둘러싸는 겁니다. 그러면 합에는 영향을 끼치지않으면서 1칸만 영향을 주는 경우를 만들수 있기때문에 상당히 유리하다는 것이죠. 그리고 오류가 나는 경우를 방지할 수도 있구요.

이 문제에서는 가장 긴 블럭이 가장 상단 위에서 좌우로 한칸씩만 놓는 경우일때를 상정해서 0을 둘러쌓으면 

상 하 좌 우 3개씩 0을 넣어서  배열을 만들때는 n값과 m값보다 +6을 더해서 배열을 잡고 (3,3)부터 숫자영역을 넣어주면 됩니다.

이 기법은 미로찾기와 같이 일정한 2차원배열로 일정 영역을 벗어나면 안되는 경우에 상당히 유용한 기법중 하나 입니다. 

2번 경우 역시 대칭이나 회전의 경우도 따져야된다는 것도 생각해봐야겠죠.  

근데 이건 머리아프게 이경우 저경우 따지는 것보다 직접 하나씩 만들어주는게 속 편하죠. 대신 대칭을해서 회전한 경우랑 같은 경우면 경우에서 빼줘야합니다.

 저희는 이 블럭 밑의 숫자를 더하면 되는거기때문에,  각 경우마다 배열의 합의 경우를 따져 주기만 하면 되는거 아닌가요?

1번부터 5번까지 각경우의 배열과 관련된 합의 경우를 만들어서 표시를 하면되는거죠. 

근데 회전을 하는 경우도 다 따로 만들어야되고, 대칭하는 경우도 다 만들어야하는데 

1번 모양 4번 모양 5번모양은 회전만 따지면되고 (대칭해도 회전하는 경우랑 같기때문에) 1번은 2개 경우 4번 5번은 4개 경우

2번은 회전, 대칭안따져도 같은 경우만 나오니까 경우는 한 개 경우 

3번은 회전, 대칭 모두 따져줘야하니까 경우자체는 조금 더 많아지겠죠. 회전경우 4개랑 회전한걸 대칭하는 경우해서 총 8개 경우를 만들어서 해야죠.

직접 코드로 보여드리면 이 합을 어떤 방식으로 만들었는지 이해가 빠를것 같습니다. 제가 주석의 순번 만든것과 같으니까 한번 확인해보면 됩니다. 

참고로 처음에는 dfs로 만들 수 있다고 생각해서 함수명이 dfs인점은 참고해주시면 좋겠습니다 ㅠ

package codeBaekJoon;

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

public class no14500_tetromino {
	static int map [][];
	static int x, y;
	static int max=0;

	static void dfs(int a, int b){
		int sum=0;
		// 1-1. 직선 case (세로 놓기)
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a+2][b];
		sum += map[a+3][b];
		if(max<sum){
			max = sum;
		}
		// 1-2 직선 case (가로 놓기)
		sum=0;
		sum += map[a][b];
		sum += map[a][b+1];
		sum += map[a][b+2];
		sum += map[a][b+3];
		if(max<sum){
			max = sum;
		} 
		// 2. 네모 case 
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a+1][b+1];
		sum += map[a][b+1];
		if(max<sum){
			max = sum;
		}
		// 3-1. ㄴ case // 왼상단시작 오른 하단 종료. (반시계방향)
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a+2][b];
		sum += map[a+2][b+1];
		if(max<sum){
			max = sum;
		}
		// 3-1-2. ㄴ case // 왼상단시작 오른 하단 종료. (반시계방향)의 대칭.
		sum=0;
		sum += map[a][b+1];
		sum += map[a+1][b+1];
		sum += map[a+2][b+1];
		sum += map[a+2][b];
		if(max<sum){
			max = sum;
		}

		// 3-2. ㄴ case // 왼하단시작 오른 상단 종료.
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a][b+1];
		sum += map[a][b+2];
		if(max<sum){
			max = sum;
		}
		// 3-2-2. ㄴ case // 왼하단시작 오른 상단 종료. 의 대
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b+2];
		sum += map[a][b+1];
		sum += map[a][b+2];
		if(max<sum){
			max = sum;
		}


		// 3-3. ㄴ case // 왼상단시작 오른 하단 종료 (시계방향) 
		sum=0;
		sum += map[a][b];
		sum += map[a][b+1];
		sum += map[a+1][b+1];
		sum += map[a+2][b+1];
		if(max<sum){
			max = sum;
		}
		// 3-3-2. ㄴ case // 왼상단시작 오른 하단 종료 (시계방향) 의 대칭
		sum=0;
		sum += map[a][b];
		sum += map[a][b+1];
		sum += map[a+1][b];
		sum += map[a+2][b];
		if(max<sum){
			max = sum;
		}
		// 3-4. ㄴ case // 오른 상단시작  왼 하단 종료
		sum=0;
		sum += map[a][b+2];
		sum += map[a+1][b+2];
		sum += map[a+1][b+1];
		sum += map[a+1][b];
		if(max<sum){
			max = sum;
		}
		// 3-4-2. ㄴ case // 오른 상단시작  왼 하단 종료 의 대칭  
		sum=0;
		sum += map[a+1][b+2];
		sum += map[a+1][b+1];
		sum += map[a+1][b];
		sum += map[a][b];
		if(max<sum){
			max = sum;
		}
		
		// 4-1. ㄴㄱ case // 왼상단시작 오른 하단 종료.  (ㄴㄱ)
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a+1][b+1];
		sum += map[a+2][b+1];
		if(max<sum){
			max = sum;
		}
		// 4-2. ㄴㄱ case // 오른 상단시작  하단 종료. 
		sum=0;
		sum += map[a][b+2];
		sum += map[a][b+1];
		sum += map[a+1][b+1];
		sum += map[a+1][b];
		if(max<sum){
			max = sum;
		}
		// 4-3. ㄴㄱ case // 왼하단시작 오른 상단 종료. 
		sum=0;
		sum += map[a+2][b];
		sum += map[a+1][b];
		sum += map[a+1][b+1];
		sum += map[a][b+1];
		if(max<sum){
			max = sum;
		}
		// 4-4. ㄴㄱ case // 왼상단시작 오른 하단 종료.  (ㄱㄴ꼴)
		sum=0;
		sum += map[a][b];
		sum += map[a][b+1];
		sum += map[a+1][b+1];
		sum += map[a+1][b+2];
		if(max<sum){
			max = sum;
		}
		// 5-1.  ㅗ  case //  ㅜ
		sum=0;
		sum += map[a][b];
		sum += map[a][b+1];
		sum += map[a][b+2];
		sum += map[a+1][b+1];
		if(max<sum){
			max = sum;
		}
		// 5-2.  ㅗ  case // ㅓ  
		sum=0;
		sum += map[a][b+1];
		sum += map[a+1][b+1];
		sum += map[a+2][b+1];
		sum += map[a+1][b];
		if(max<sum){
			max = sum;
		}
		// 5-3.  ㅗ  case //  ㅗ  
		sum=0;
		sum += map[a+1][b];
		sum += map[a+1][b+1];
		sum += map[a+1][b+2];
		sum += map[a][b+1];
		if(max<sum){
			max = sum;
		}	
		// 5-4.  ㅗ  case //  ㅏ  
		sum=0;
		sum += map[a][b];
		sum += map[a+1][b];
		sum += map[a+2][b];
		sum += map[a+1][b+1];
		if(max<sum){
			max = sum;
		}


	}



	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String p = br.readLine();
		StringTokenizer st = new StringTokenizer(p, " ");
		y = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		map = new int[x+6][y+6];
		for(int i = 3; i<y+3; i++){
			p = br.readLine();
			st = new StringTokenizer(p, " ");
			for(int j = 3; j<x+3; j++){
				map[j][i] = Integer.parseInt(st.nextToken());
			}
		}
		for(int j=0; j<x+3; j++){
			for(int i=0; i<y+3; i++){
				dfs(j, i);  //x, y랑 값바꿔서 틀림...
			}
		}
		System.out.println(max);
/*
			for(int i = 0; i<y+6; i++){
			for(int j = 0; j<x+6; j++){
				System.out.print(map[j][i]+" ");
			}
			System.out.println();
		}*/
	}
}

 

이렇게 한다면, 무리 없이 답이 나올 겁니다. 

감사합니다. 다음번에도 삼성 SW역량테스트 문제로 찾아뵙도록 하겠습니다.