BOJ 14500 테트로미노 java 자바

BOJ 14500 테트로미노 java 자바

 

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

14500번: 테트로미노

 

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

public class Main {
	static int N, M;
	static int[][] grid;
	static int[][] dir = { 
			{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }
	};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		grid = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {	
				visited[i][j] = true;
				solve(i, j, 1, grid[i][j]);
				visited[i][j] = false;
				solve2(i, j);
			}
		}
		
		System.out.println(MAX);

	} // main

	static int MAX = 0;
	static boolean[][] visited;
	private static void solve(int x, int y, int cnt, int sum) {
		for (int d = 0; d < 4; d++) {
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];
			if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue;
			visited[nx][ny] = true;
			if(cnt == 3) {
				MAX = Math.max(MAX, sum+grid[nx][ny]);
				visited[nx][ny] = false;
				continue;
			}
			solve(nx, ny, cnt+1, sum+grid[nx][ny]);
			visited[nx][ny] = false;
		}
		
	} // solve
	
	static int[][][] blocks = {
			{{-1, 0},{0, -1},{0, 1}},	
			{{-1, 0},{0, 1},{1, 0}},	
			{{0, -1},{0, 1},{1, 0}},	
			{{-1, 0},{0, -1},{1, 0}},	
	};
	private static void solve2(int x, int y) {
		for (int b = 0; b < 4; b++) {
			int sum = grid[x][y];
			boolean pass = true;
			for (int d = 0; d < 3; d++) {
				int nx = x + blocks[b][d][0];
				int ny = y + blocks[b][d][1];
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) {
					pass = false;
					break;
				}
				sum += grid[nx][ny];
			}
			if(pass) {
				MAX = Math.max(MAX, sum);
			}
		}
		
	} // solve2

}

 

 

여러가지 방법을 시도하다가 조금 힌트를 보고 풀었다.. 하하

처음에 dfs로 했다가 ㅗ ㅓ ㅜ ㅏ 모양을 할 수가 없어 bfs로 바꿨다가 bfs로는 방문체크가 불가능해 안 될 것 같았고

그래서 다시 dfs로 돌아와 ㅗ ㅓ ㅜ ㅏ 해결을 위해 참고를 했다

그냥 ㅗ ㅓ ㅜ ㅏ 는 따로 배열을 만들어 한 번 더 체크를 해주면 끝날 일... 이었다.

 

	static int[][][] blocks = {
			{{-1, 0},{0, -1},{0, 1}},	
			{{-1, 0},{0, 1},{1, 0}},	
			{{0, -1},{0, 1},{1, 0}},	
			{{-1, 0},{0, -1},{1, 0}},	
	};

 

이렇게 ㅗ ㅓ ㅜ ㅏ 중앙을 x, y 라고 했을 때 모양을 만들어 4개 다 체크해보고 max 나오면 갱신하면 된다.

 

나머지

이 모양들은 일반적인 dfs로 깊이 4가 될 때까지 들어가면 된다.