[Java] 백준 3085번 사탕 게임

4가지 종류의 사탕이 있을 때 인접한 두개의 사탕 위치를 바꿔서 종류가 같은 가장 긴 사탕 수열을 만드는 문제입니다.

사탕의 개수가 50*50개이므로 모든 경우의 수를 탐색해보았습니다.
인접한 사탕과 변경된 모든 경우에서 가장 긴 수열을 찾아서 출력해주었습니다.

import java.util.Scanner;

public class Main{	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s;
		int[][] arr = new int[n+2][n+2];
		int ans = 0;
		for(int i=1; i<=n; ++i) {
			s = sc.next();
			for(int j=0; j<n; ++j) {
				if(s.charAt(j) == 'C') {
					arr[i][j+1] = 1;
				} else if(s.charAt(j) == 'P') {
					arr[i][j+1] = 2;
				} else if(s.charAt(j) == 'Z') {
					arr[i][j+1] = 3;
				} else if(s.charAt(j) == 'Y') {
					arr[i][j+1] = 4;
				}
			}
		}
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				if(arr[i+1][j] != 0) {
					swap(arr, i, j, i+1, j);				
					ans = Math.max(ans, find(arr, arr[i][j], i, j));
					ans = Math.max(ans, find(arr, arr[i+1][j], i+1, j));
					swap(arr, i, j, i+1, j);
				}
				if(arr[i][j+1] != 0) {
					swap(arr, i, j, i, j+1);
					ans = Math.max(ans, find(arr, arr[i][j], i, j));
					ans = Math.max(ans, find(arr, arr[i][j+1], i, j+1));
					swap(arr, i, j, i, j+1);
				}
			}
		}
		System.out.println(ans);
	}
	
	public static void swap(int[][] arr, int ai, int aj, int bi, int bj) {
		int tmp;
		tmp = arr[ai][aj];
		arr[ai][aj] = arr[bi][bj];
		arr[bi][bj] = tmp;
	}
	public static int moveFind(int[][] arr, int num, int y, int x, int d, int c) {
		if(d == 0) {
			x += -1;
		} else if(d == 1) {
			x += 1;
		} else if(d == 2) {
			y += -1;
		} else if(d == 3) {
			y += 1;
		}
		if(num == arr[y][x]) {
			c = moveFind(arr, num, y, x, d, c + 1);
		}
		return c;
	}
	public static int find(int[][] arr, int num, int y, int x){
		int ans = 0;
		ans = Math.max(ans, moveFind(arr, num, y, x, 0, 0) + moveFind(arr, num, y, x, 1, 0) + 1);
		ans = Math.max(ans, moveFind(arr, num, y, x, 2, 0) + moveFind(arr, num, y, x, 3, 0) + 1);
		return ans;
	}
}