[백준] code.plus(브루트포스,JAVA)14500번, 테트로미노

문제 링크

14500번: 테트로미노

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에서 블록의 회전과 대칭의 모든 경우를 각 배열의 값마다 적용시켜서 진행하는 방법을 생각하였으나 경우의 수 생각보다 많을 것 같다고 생각하였습니다.

그래서 검색을 해보았는데 DFS(깊이우선탐색)을 이용해서 문제를 해결할 수 있는 것을 알게되었습니다.

테트로미노 도형에서 DFS을 이용해서 확인할 수 있는 도형은 'ㅜ'을 제외한 모형입니다.

dfs할 때에 테트로미노 모형은 모두 4개의 정사각형을 가지고 있기 때문에 깊이를 4일 때까지 진행합니다.이유는 자세히 예제를 들어 설명해드리겠습니다.예제입력 1을 기준으로 설명해보도록 하겠습니다.(배열의 기준값을 x=0, y=0 가정하겠습니다.)깊이를 상/하/좌/우 순으로 탐색해보겠습니다.(x=0,y=0은 상/좌 방향으로 갈 수 없기 때문에 하/우로 깊이로 탐색합니다.)

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

1. '하' 방향 탐색(테트로미노 도형 하나 완성)

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

2. x=1, y=0에서 '우'로 갔을 때

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(↓)	2	3	4	5
5(→)	4(↑)	3	2	1
2	3	4	5	6
6	5	4	3	2
1	2	1	2

1(↓)	2	3	4	5
5(→)	4(↓)	3	2	1
2	3	4	5	6
6	5	4	3	2
1	2	1	2

3. x=2,y=0에서 '우'로 갔을 때

1(↓)	2	3	4	5
5(↓)	4	3	2	1
2(→)	3	4	5	6
6	5	4	3	2
1	2	1	2

위 과정처럼 기준점에서 상/하/좌/우를 통해서 테트로미노 모형을 모두 확인하고 최대값을 구할 수 있습니다.

하지만 'ㅜ', 'ㅏ', 'ㅜ', 'ㅓ'은 dfs로 표현할 수 없기 때문에 따로 한번 더 확인해주어야 합니다.

'X'로 표시된 지점을 배열의 기준값으로 최대값이 존재하는지 확인하였습니다.

1. 배열 각 꼭짓점은 'ㅜ', 'ㅏ', 'ㅜ', 'ㅓ'의 도형을 만들 수 없습니다.

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

2. 배열 x = 0일 때에는 'ㅜ' 모형만 가능하다.

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

3. 배열 x = arr.lenght-1일 때 'ㅗ' 모형만 가능하다.

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

4. 배열 y = 0일 때 'ㅏ' 모형만 가능하다.

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

5. 배열 y = arr.length-1일 때 'ㅓ' 모형만 가능하다.

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

6. 위에 나머지 x,y의 해당하는 값은 'ㅗ', 'ㅓ', 'ㅏ', 'ㅜ' 모형 모두 만들 수 있습니다.

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

문제에 해결알고리즘은

1. 배열의 값에 대하여 dfs를 통해 'ㅜ' 모형을 제외한 모형의 값을 구합니다.

2. 이후 'ㅜ'모형의 회전의 대한 값을 구합니다.

3. 배열의 값에 대한 모형을 비교해서 최대값을 저장합니다.

4. 위 과정을 반복하여 배열의 값을 모두 진행한 뒤 최대값을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringToknizer을 이용하여 종이의 값들을 배열에 저장하였습니다.
• dfs/'ㅜ'모형 최대값 구하는 dfs/notDfsShapeCal함수를 만들었습니다.
• visit/board 배열을 사용하여 dfs와 notDfsShapeCal을 실행하여 최대값을 구하였습니다.
• BufferedWriter에 테트로미노의 모형 중 최대값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 상/하/좌/우를 이동하도록 dx와 dy를 사용하여 탐색하였으며 깊이가 4가 되면 최대값을 비교하도록 하였습니다.
• notDfsShapeCal은 'ㅜ', 'ㅏ', 'ㅓ', 'ㅗ'을 위에서 설명한 조건에 따라 최대값을 구하여 dfs에서 구한 최대값과 비교하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] board;	//종이 값 저장 배열
	static boolean[][] visit;		//종이 방문 여부 확인 배열
   	//상하좌우 이동 x,y 관련 값
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int result = Integer.MIN_VALUE,N,M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----입력값 저장 및 배열 초기화-----------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = 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++)
        		board[i][j] = Integer.parseInt(st.nextToken());
        }
        //-----배열의 각 값 dfs와 'ㅜ' 모형 함수 실행
        for(int i=0;i<N;i++) {
        	for(int j=0;j<M;j++) {
        		visit[i][j] = true;
        		dfs(i, j, 1, board[i][j]);
        		notDfsShapeCal(i, j);
        		visit[i][j] = false;
        	}
        }
        bw.write(result + "\n");	//결과 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------dfs를 통해 'ㅜ'제외한 모형 최대값 찾는 함수---------
    public static void dfs(int x, int y, int depth, int sum) {
    	if(depth==4) {		//깊이가 4일 때
    		result = Math.max(result, sum);
    		return;
    	}
        //깊이가 4가 아닐 때 상하좌우 깊이탐색
    	for(int i=0;i<4;i++) {
    		int tempX = x + dx[i];
    		int tempY = y + dy[i];
    		if(tempX>-1 && tempX<N && tempY>-1 && tempY<M && !visit[tempX][tempY]) {
    			visit[tempX][tempY] = true;
    			dfs(tempX, tempY, depth+1, sum + board[tempX][tempY]);
    			visit[tempX][tempY] = false;
    		}
    	}
    }
    //------'ㅜ'모형 관련 최대값 찾는 함수-------
    public static void notDfsShapeCal(int x, int y) {
    	int sum = board[x][y];
        //꼭짓점일 경우
    	if((x==0 || x==N-1) && (y==0||y==M-1)) {
    		sum = -1;
    	}else if(x==0) {	//x = 0일 때 'ㅜ'
    		sum += board[x][y-1] + board[x][y+1] + board[x+1][y];
    	}else if(x==N-1) {	//x = arr.length-1일 때 'ㅗ'
    		sum += board[x][y-1] + board[x][y+1] + board[x-1][y];
    	}else if(y==0) {	//y = 0일 때 'ㅏ'
    		sum += board[x-1][y] + board[x+1][y] + board[x][y+1];
    	}else if(y==M-1) {	//y = arr.length-1 'ㅓ'
    		sum += board[x-1][y] + board[x+1][y] + board[x][y-1];
    	}else {		// 그 이외에 'ㅜ', 'ㅗ', 'ㅓ', 'ㅏ'
    		sum +=  board[x][y-1] + board[x][y+1] + board[x+1][y];
    		sum = Math.max(sum, board[x][y-1] + board[x][y+1] + board[x-1][y] + board[x][y]);
    		sum = Math.max(sum, board[x-1][y] + board[x+1][y] + board[x][y+1] + board[x][y]);
    		sum = Math.max(sum, board[x-1][y] + board[x+1][y] + board[x][y-1] + board[x][y]);
    	}
    	result = Math.max(result, sum);	//최대값 비교
    }
}