Baekjoon 3085 사탕 게임 JAVA

3085번: 사탕 게임

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

풀이

처음에 접근한 방식은 배열안에서 연속되어 진행되는 경우가 아닐때, 아닌것의 대각선을 체크하는 방법이었다.

문제의 조건상 경우의 수가 그렇게 많지 않아서 brute force로도 가능하다고 판단하였다.

swap을 이용하여 모든 경우의 수를 하나씩 만들어 준다. 그리고 동시에 연속되는 경우를 체크하여 가장 연속되는 경우가 많은 것을 답으로 채택한다.

코드

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

public class Main {
	static int max = 0, n;
	static char[][] arr = new char[50][50];

	public static void check() {
		int tmp = 0;
		for (int i = 0; i < n; i++) {
			tmp = 1;
			for (int j = 0; j < n-1; j++) {
				if (arr[i][j] == arr[i][j + 1])
					tmp++;
				else
					tmp=1;
				if(tmp>max)
					max=tmp;
			}
		}
		for(int j=0;j<n;j++) {
			tmp=1;
			for(int i=0;i<n-1;i++) {
				if(arr[i][j]==arr[i+1][j])
					tmp++;
				else
					tmp=1;
				if(tmp>max)
					max=tmp;
			}
		}
	}
	
	public static void swapy(int i,int j) {
		char temp=arr[i][j];
		arr[i][j]=arr[i+1][j];
		arr[i+1][j]=temp;
	}
	
	public static void swapx(int i,int j) {
		char temp=arr[i][j];
		arr[i][j]=arr[i][j+1];
		arr[i][j+1]=temp;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++)
			arr[i] = br.readLine().toCharArray();

		for(int i=0;i<n;i++) {
			for(int j=0;j<n-1;j++)
			{
				swapx(i,j);
				check();
				swapx(i,j);
			}
		}
		
		for(int j=0;j<n;j++) {
			for(int i=0;i<n-1;i++)
			{
				swapy(i,j);
				check();
				swapy(i,j);
			}
		}

		System.out.println(max);
	}
}