BOJ - 테트로미노 14500번 (JAVA)

❓ 문제 - 백준 테트로미노 14500번 - JAVA 풀이법

출처 

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

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 각 모양의 회전, 대칭한 모양 모두 다 구현으로 만든 후 해당 모양에 해당하는 MAP에 숫자를 더해서 최대값을 갱신하도록 구현하였다. 
• 밑의 모양에서 색깔있는 부분은 1로 만약 네모틀 안에 모양인 부분을 제외한(색깔없는) 부분은 -1로 해서 1일 때만 해당 모양으로 인식할 수 있게 코딩하였다.

2. 느낀점

• 바로 이 문제 보자마자 빡구현이겠다 싶어서 각 모양에 잘 맞춰 구현했지만 나중에 다른 풀이들도 참고해보니 DFS를 활용하면 좀 더 간결하게 최대값을 구해낼 수 있더라..
• 근데 둘 다 백준에서 돌려보니 빡구현의 경우 DFS를 사용한 방법보다 2배 이상은 빠르더라..!
• 하지만 DFS의 신박한 아이디어를 느끼실 분들은 다른 분들의 코드도 참고해보시면 좋을 것 같습니다 ㅎㅎ

 

 

💻 소스코드

// BOJ - 테트로미노(14500번)
// 구현

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

public class Main_14500 {

	public static int[][][] tetromino = 
		{{{1, 1, 1, 1}}, //ㅡ 
		 {{1}, {1}, {1}, {1}}, //ㅣ
		 {{1, 1},{1, 1}}, //ㅁ
		 {{1, -1}, {1, -1}, {1, 1}}, //L
		 {{1, 1, 1}, {1, -1, -1}},
		 {{1, 1}, {-1 ,1}, {-1, 1}},
		 {{-1, -1, 1}, {1, 1, 1}},
		 {{-1, 1}, {-1, 1}, {1, 1}},
		 {{1, 1, 1}, {-1, -1, 1}},
		 {{1, 1}, {1, -1}, {1, -1}},
		 {{1, -1, -1}, {1, 1, 1}},
		 {{1, -1}, {1, 1}, {-1, 1}}, //Z
		 {{-1, 1, 1}, {1, 1, -1}},
		 {{-1, 1}, {1, 1}, {1, -1}},
		 {{1, 1, -1}, {-1, 1, 1}},
		 {{1, 1, 1}, {-1, 1, -1}}, //ㅜ
		 {{-1 ,1}, {1, 1}, {-1, 1}},
		 {{-1, 1, -1}, {1, 1, 1}},
		 {{1, -1}, {1, 1}, {1, -1}},
		 };

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] 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());
			}
		}
		int ans = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				outer:for(int t=0;t<tetromino.length;t++) {
					int sum = 0;
					for(int p=0;p<tetromino[t].length;p++) {
						for(int q=0;q<tetromino[t][p].length;q++) {
							int x = i + p;
							int y = j + q;

							if(x < 0 || x >= n || y < 0 || y >=m) continue outer;
							if(tetromino[t][p][q] == 1) {
								sum += map[x][y];
							}
						}
					}
					ans = Math.max(ans, sum);
				}
			}
		}

		System.out.println(ans);


	}

}