[백준] code.plus(브루트포스,JAVA)3085번, 사탕 게임

문제 링크

3085번: 사탕 게임

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

 

이 문제는 주어진 조건에 대하여 모든 경우의 수를 확인해보고 사탕을 먹을 수 있는 가장 큰 값을 출력하면 됩니다.

 

각 배열의 값마다 가로와 세로로 변경을 진행해보고 먹을 수 있는 캔디의 최대 개수를 구한 뒤에 다시 원래 상태로 복구하는 것이 중요합니다.

 

문제에 해결알고리즘은

1. 배열의 값을 기준으로 가로 변경 및 세로 변경을 진행합니다.

2. 변경한 배열에서 최대로 먹을 수 있는 캔디 수를 구하여 전체 최대값과 비교합니다.

3. 배열에 상태를 원상태로 바꾸어줍니다.

※ 배열 Row이 배열크기-1이 되었을 때에는 세로로 변경이 불가능합니다.(아래 표 파란색)

※ 배열 Col이 배열크기-1이 되었을 때에는 가로로 변경이 불가능합니다.(아래 표 빨간색)

※ 배열 Row = 배열크기 -1, Col = 배열크기 - 1일 때에는 가로 , 세로 모두 변경이 불가능합니다.(아래표 초록색)

이유는 표로 보여드리겠습니다.(예제 입력 1에 대한 표)

C	C	P
C	C	P
P	P	C

표에 빨간색 글자는 오른쪽 가로로 변경하지 못하기 때문에 세로 변경만 진행합니다.

표에 파란색 글자는 아래 세로로 변경하지 못하기 때문에 가로 변경만 진행합니다.

표에 초록색 글자는 가로, 세로 모두 변경하지 못합니다.

• BufferedReader를 사용하여 입력 값을 배열에 저장하였습니다.
• 가로 변경/세로 변경하는 candiRowChange/candiColChange함수를 만들었습니다.
• 열·행 최대값/가로·세로 변경의 최대값 구하는 candiCheck/maxCandi 함수를 만들었습니다.
• 배열에 값들을 maxCandi 함수를 실행하여 전체적 최대값을 구하였습니다.
• BufferedWriter에 먹을 수 있는 캔디의 최대값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• maxCandi은 row와 col의 값에 따라 위에 설명한 대로 가로/세로를 변경해주어 해당 인덱스값의 먹을 수 있는 캔디의 최대값을 구하였습니다.
• candiRowChange은 가로 변경시 캔디에 색깔을 변경하도록 하였습니다.
• candiColChange은 세로 변경시 캔디에 색깔을 변경하도록 하였습니다.
• candiCheck은 가로 기준, 세로 기준으로 각각 변경된 배열에서 먹을 수 있는 최대의 캔디를 구하도록 하였습니다.

 

결과 코드

import java.io.*;
public class Main{
	static char[][] candis;		//캔디 색깔 저장 배열
	static int N;			//배열 크기
    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
        //-------입력값 저장 및 배열 초기화---------
        N = Integer.parseInt(br.readLine());
        int result = Integer.MIN_VALUE;
        candis = new char[N][N];
        for(int i=0;i<N;i++) {
        	String temp = br.readLine();
        	for(int j=0;j<N;j++) {
        		candis[i][j] = temp.charAt(j);
        	}
        }
        //------배열의 각 값 변경에 의한 먹을 수 있는 캔디의 최대값 구하기-------
        for(int i=0;i<N;i++) {
        	for(int j=0;j<N;j++) {
        		result = Math.max(result, maxCandi(i, j));
        	}
        }
        bw.write(result + "\n");		//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------변경이후 먹을 수 있는 캔디의 최대값 구하는 함수----------
    public static int maxCandi(int x, int y) {
    	int max = Integer.MIN_VALUE;
    	if(x == N-1 && y==N-1)	//row,col이 N-1값일 때
    		return -1;
    	if(x==N-1) {	//row가 N-1일 때 가로변경만 진행
    		candiRowChange(x, y);
    		max = Math.max(max, candiCheck());
    		candiRowChange(x, y);
    	}else if(y==N-1) {	//Col이 N-1일 때 세로 변경만 진행
    		candiColChange(x, y);
    		max = Math.max(max, candiCheck());
    		candiColChange(x, y);
    	}else {		//가로 및 세로 변경 모두 진행
    		candiRowChange(x, y);
    		max = Math.max(max, candiCheck());
    		candiRowChange(x, y);
    		
    		candiColChange(x, y);
    		max = Math.max(max, candiCheck());
    		candiColChange(x, y);
    	}
    	return max;
    }
    //---------가로 변경 함수--------
    public static void candiRowChange(int x, int y) {
    	char temp = candis[x][y];
    	candis[x][y] = candis[x][y+1];
    	candis[x][y+1] = temp;  	
    }
    //---------세로 변경 함수---------
    public static void candiColChange(int x, int y) {
    	char temp = candis[x][y];
    	candis[x][y] = candis[x+1][y];
    	candis[x+1][y] = temp;  	
    }
    //--------변경 후 캔디 최대값 구하는 함수------
    public static int candiCheck() {
    	char cur;
    	int count=0;
    	int result = Integer.MIN_VALUE;
        //------가로 기준 최대값-------
    	for(int i=0;i<N;i++) {
    		cur = candis[i][0];
    		count = 1;
    		for(int j=1;j<N;j++) {
    			if(cur==candis[i][j])
    				count++;
    			else {
    				result = Math.max(result, count);
    				count = 1;
    				cur = candis[i][j];
    			}
    		}
        	result = Math.max(result, count);
    	}
        //---------세로 기준 최대값-------
    	for(int i=0;i<N;i++) {
    		cur = candis[0][i];
    		count = 1;
    		for(int j=1;j<N;j++) {
    			if(cur==candis[j][i])
    				count++;
    			else {
    				result = Math.max(result, count);
    				count = 1;
    				cur = candis[j][i];
    			}
    		}
        	result = Math.max(result, count);
    	}
    	return result;
    }
}