[백준 JAVA] 14500 테트로미노

문제

---

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

 

 

풀이방법

---

처음에는 모든 모양을 다 고려해서 풀어야하는 줄 알았는데 시간 제한을 보니 그렇게 풀 수 없는 문제였다.

 

다음에 생각해낸 방법은 dfs를 사용하는 것이다.

dfs를 사용하면 ㅗ,ㅜ,ㅓ,ㅏ를 제외한 모든 모양을 만들어낼 수 있고, 그 중에서 최대값을 찾으면 된다.

4방탐색을 진행하며 sum에 map값을 더해준 값을 매개변수로 계속 전달하고, 그중에서 최대값을 찾는다.

 

그 외의 ㅗ,ㅜ,ㅓ,ㅏ는 각각의 범위를 확인하고, getcount함수를 사용해서 하나 하나 세어줬다.

코드는 아래와 같다.

코드

---

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

public class Main{
	
	static int[][] del = {{-1,0},{1,0},{0,-1},{0,1}};
	static int map[][];
	static int N,M;
	static boolean visit[][];
	static int num;
	static int max=Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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());
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				visit[i][j]=true;
				dfs(i,j,1,map[i][j]);
				visit[i][j]=false;
				getcount(i,j);
			}
		}

		System.out.println(max);
		
	}
	

	static void dfs(int x, int y,int cnt,int sum) {
		if(cnt==4) {
			max=Math.max(max, sum);
			return;
		}
		for(int i=0; i<4; i++) { //4방 탐색을 진행하면서
			int nx=x + del[i][0];
			int ny=y + del[i][1];
			
			if(nx>=0 && nx<N && ny>=0 && ny<M && visit[nx][ny]==false) {
				visit[nx][ny]=true;
				dfs(nx,ny,cnt+1,sum+map[nx][ny]);
				visit[nx][ny]=false;
			}
			
			
		}

	}
	
	static void getcount(int x, int y) {
		//ㅜ
		int getsum1=0;
		if(y-1>=0 && y+1<M && x+1<N ) {
			getsum1=map[x][y-1]+map[x][y+1]+map[x][y]+map[x+1][y];
		}
		max=Math.max(getsum1, max);
		//ㅗ
		int getsum2=0;
		if(y-1>=0 && y+1<M && x-1>=0 ) {
			getsum2=map[x][y-1]+map[x][y+1]+map[x][y]+map[x-1][y];
		}
		max=Math.max(getsum2, max);
		//ㅓ
		int getsum3=0;
		if(y-1>=0 && x+1<N && x-1>=0) {
			getsum3=map[x][y-1]+map[x+1][y]+map[x][y]+map[x-1][y];
		}
		max=Math.max(getsum3, max);
		//ㅏ
		int getsum4=0;
		if(x-1>=0 && y+1<M && x+1<N ) {
			getsum4=map[x][y+1]+map[x+1][y]+map[x][y]+map[x-1][y];
		}
		max=Math.max(getsum4, max);
	}

}