[BOJ_3085/JAVA] 사탕 게임

문제

풀이

해당 문제는 완전탐색을 이용하여 문제를 풀면 된다. 

나는 문제를 잘못이해해서 처음부터 끝까지 인접한 사탕을 바꿀 수 있는대로 다 바꿔서 최댓값을 구하는 줄 알아서 조금 헤맸다...

알고보니 가로, 세로 둘 중 한번만 바꿨을 때 먹을 수 있는 사탕의 최댓값을 구하는 문제이다.

 

사탕개수 구하는 순서는 다음과 같다.

1. 가로로 인접한 사탕을 서로 바꾸고 사탕개수 최댓값 저장

2. 세로로 인접한 사탕을 서로 바꾸고 사탕개수 최댓값 저장

 

근데 주의할 점은 인접한 사탕을 바꾸고 다시 원래대로 돌려놔야 한다.

위 순서대로 하면 가로로 바꾼 사탕개수와 세로로 바꾼 사탕개수 중 최댓값을 구하게 된다.

 

코드

package Week08;

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

public class BOJ3085 {
	
	static int n;
	static char [][]map;
	static int max=0;
	static int count=1;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n=Integer.parseInt(br.readLine());
		map = new char[n][n];
		
		for(int i=0;i<n;i++) {
			String s = br.readLine();
			
			for(int j=0;j<n;j++) {
				map[i][j]=s.charAt(j);
			}
		}
		
		// 가로로 인접한 두 사탕 교환하고 최대 사탕개수 구하기
		for(int i=0;i<n;i++) {
			for(int j=0;j<n-1;j++) {
				char temp=map[i][j];
				map[i][j]=map[i][j+1];
				map[i][j+1]=temp;
				
				// 바꾼 사탕을 기준으로 최대 사탕개수 구하기
				check();
				
				// 교환한 사탕 복구
				temp=map[i][j];
				map[i][j]=map[i][j+1];
				map[i][j+1]=temp;
			}
		}
		
		// 세로도 동일
		for(int i=0;i<n;i++) {
			for(int j=0;j<n-1;j++) {
				char temp=map[j][i];
				map[j][i]=map[j+1][i];
				map[j+1][i]=temp;
				
				check();
				
				temp=map[j][i];
				map[j][i]=map[j+1][i];
				map[j+1][i]=temp;
			}
		}
		
		System.out.println(max);
	}
	
	// 가로, 세로로 비교해서 먹을 수 있는 최댓값 구하기
	public static void check() {
		
		//가로로 비교
		for(int i=0;i<n;i++) {
			count=1;
			for(int j=0;j<n-1;j++) {
				
				//  사탕이 다른 경우 초기화
				if(map[i][j]!=map[i][j+1]) {
					count=1;
				}
				// 사탕이 같은 경우 사탕 한개 먹기
				else {
					count++;
				}
				
				// 사탕 최대개수
				max = Math.max(count, max);
			}
		}
		
		//세로로 비교
		for(int i=0;i<n;i++) {
			count=1;
			for(int j=0;j<n-1;j++) {
				
				// 사탕이 다른 경우 초기화
				if(map[j][i]!=map[j+1][i]) {
					count=1;
				}
				// 사탕이 같은 경우 
				else {
					count++;
				}
				
				max = Math.max(count, max);
			}
		}
	}

}