[ 백준 ][ 자바 ][ 14500] 테트로미노

문제가 굉장히 까다로울 것 같은 문제였다

나는 와 설마 이거 생김새대로 회전이랑 대칭을 구현하고 해야하나

란 생각에 잠겼다...

그런데 다른 사람들 보니 dfs로 4 depth까지만 진행하면 된다고 했다.

하나하나 그려보니...정말 그렇더라

어...엄청 간단한 문제였네...?

그런데 그냥 bfs로 움직이면 될듯 싶어서 bfs로 진행했는데

시간초과가..걸렸다

visited 배열을 만드는 과정이 분명 문제 같은데

...음 방법이 딱히 생각나지않았다... 익숙치않는 dfs로 한번 짜봤다. 

확실하게 dfs가 콤팩트하긴 한거같다. 

[ㅗ] 모양은 하나하나 돌려가며 비교했다.

후 성공~집에 가즈아.ㅜ

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

//좌측 상단부터 1,2,3,4,5로 번호를 매기자면
//dfs를4번만
//ㅗ 모양 블록 돌리기 
//5 5
//1 2 3 4 5
//5 4 3 2 1
//2 3 4 5 6
//6 5 4 3 2
//1 2 1 2 1

class TPoint {
	int x;
	int y;
	int value;
	TPoint(int y, int x, int value){
		this.y = y;
		this.x = x; 
		this.value = value;
	}
}
public class Main {
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int N;
	static int M;
	static Queue q = new LinkedList();
	static int MAX;
	static int[][] MAP = new int[501][501];
	static boolean[][] visited = new boolean[501][501];
	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() );
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int idx = 0;
			while(st.hasMoreTokens()) {
				MAP[i][idx] = Integer.parseInt(st.nextToken());
				idx += 1;
			}
		}
		//printMap();
		for(int i = 0 ; i < N; i++) {
			for(int j = 0; j < M; j++) {
				visited[i][j] = true;
				dfs_4(0, MAP[i][j], i, j);
				visited[i][j] = false;
				blockF(i, j);
			}
		}
//		dfs_4(0, MAP[3][0], 3, 0);
//		blockF(3,0);
		//blockF(0,1);
		System.out.println(MAX);
	
	}
	public static void blockF(int y, int x) {
		
		int value = MAP[y][x];
		
		for(int disable =0; disable < 4; disable++) {
			for(int i = 0; i < 4; i++) {
				int yy = dy[i] + y;
				int xx = dx[i] + x;
				if( disable == i ) {
					continue;
				}
				if( yy >= 0 && yy < N && xx >= 0 && xx < M ) {
					//System.out.println(yy +" "+xx);
					value += MAP[yy][xx];
					//System.out.println(value);
				}				
				
			}
			if( MAX <= value) {
				MAX = value;
			}
			value = MAP[y][x];
		}
	
	}
	public static void dfs_4(int depth, int value, int y, int x) {
		if( depth == 3) {
			return;
		}
		
		for(int i = 0 ; i < 4; i++) {
			int yy = dy[i] + y;
			int xx = dx[i] + x;			
			if(yy >= 0 && yy < N && xx >= 0 && xx < M ) {
				
				if(!visited[yy][xx]) {
					//System.out.println(yy + " " + xx);
					int nowValue = MAP[yy][xx] + value;
					//System.out.println(nowValue);
					if( MAX <= nowValue) {
						MAX = nowValue;
					}
					
					visited[yy][xx] = true;
					dfs_4(depth + 1, nowValue, yy, xx);
					visited[yy][xx] = false;
				}
			}
		}
		
	}
	/* 시간초과 */
	public static void bfs_4(int y, int x) {
		visited = new boolean[N+1][M+1];
		int count = 0; 
		q.clear();
		q.add(new TPoint(y,x, MAP[y][x]));
		visited[y][x] = true;
 		while(!q.isEmpty()) {
			int qsize = q.size();
			for(int s = 0; s < qsize; s++) {
				TPoint tp = q.poll();	
				for(int i = 0 ; i < 4; i++) {
					int yy = dy[i] + tp.y;
					int xx = dx[i] + tp.x;
					if(yy >= 0 && yy < N && xx >= 0 && xx < M ) {
						if(!visited[yy][xx]) {	
							//System.out.println(yy+ " " + xx);
							int value = MAP[yy][xx] + tp.value;
							if( MAX <= value) {
								MAX = value;
							}
							//System.out.println("value " +value);
							visited[yy][xx] = true;
							q.add(new TPoint(yy, xx, value));
						}
					}
				}
			}
			count += 1;
			//printvMap();
			//System.out.println("count "+  count);
			if( count == 3) {
				return;
			}
		}
		
	}
	public static void printvMap() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(visited[i][j]) {
					System.out.print("1 ");
				}else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
	}
	public static void printMap() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
}