테트로미노 [백준 14500][골드5][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

14500번: 테트로미노

1. DFS를 이용하여 최대값4까지 탐색하여 저장한 후 MAX에 저장

2. 큐를 이용하여 ㅗ 모양 테트로미노의 최대값을 저장

3. 둘을 비교

처음에 Scanner로 Input을 받았는데 시간초과가 났다.

그리고 ㅗ 테트로미노를 처리하는데 조합을 사용했는데 너무 오래 걸리는 듯 해서 로직을 바꿨다.

import java.io.*;
import java.util.*;

public class 테트로미노 {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int N,M;
	public static boolean[][] visit;
	public static int[][] map;
	public static int sum;
	public static int[] num;
	public static boolean[] v;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visit = new boolean[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());
				sum+= map[i][j];
			}
		}
		
		int max = Integer.MIN_VALUE;
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visit[i][j] = true;
				max = Math.max(dfs(i,j,1,0), max);
				visit[i][j] = false;
				max = Math.max(bfs(i,j), max);
			}
		}
		System.out.println(max);
	}
	public static int dfs(int row, int col, int cnt,int ans) {
		if(cnt == 4) {
			return ans+map[row][col];
		}
		int result= Integer.MIN_VALUE;
		for (int i = 0; i < 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
				continue;
			}
			if(visit[nx][ny]) continue;
			visit[nx][ny] = true;
			result = Math.max(dfs(nx,ny,cnt+1,ans + map[row][col]), result);
			visit[nx][ny] = false;
		}
		return result;
	}
	public static int bfs(int row, int col) {
		 if((row == 0 || row == N-1) && (col == 0 || col == M-1)) return -1;
		 
		Queue<int[]> q = new LinkedList<>();
		
		q.add(new int[] {row,col});
		int result = map[row][col]; //시작점
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = pos[0] + dx[i];
				int ny = pos[1] + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
					continue;
				}
				q.add(new int[] {nx,ny});
			}
			if(q.size() == 3) {
				//ㅗ 모양
				while(!q.isEmpty()) {
					int[] pos2 = q.poll();
					result += map[pos2[0]][pos2[1]];
				}
			}
			else if(q.size() == 4) {
				num = new int[4];
				int Result= 0;
				
				for (int i = 0; i < 4; i++) {
					int[] pos2 = q.poll();
					Result += map[pos2[0]][pos2[1]]; //총 합 계산
					num[i]  = map[pos2[0]][pos2[1]]; //한개씩 넣기
				}
				int m = Integer.MIN_VALUE;
				for (int i = 0; i < 4; i++) {
					m = Math.max(Result - num[i], m);
				}
				
				result += m;
			}
			else return -1;
		}
		return result;
	}
}