백준 3085 / 사탕게임

문제

풀이

설명

NxN 크기의 테이블에 사탕이 있다.
인접한 두 칸을 고르고, 사탕을 교환한다.

그 다음, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제

시간복잡도 : NxN 크기의 테이블을 가지고 있으므로 O(n^2)이다.

코드

import java.util.Scanner;

public class Num3085 {

		static int check(char[][] a) {
	        int n = a.length;
	        int ans = 1;
	        
	        for (int i=0; i<n; i++) {
	            int cnt = 1;
	            for (int j=1; j<n; j++) {
	                if (a[i][j] == a[i][j-1]) {
	                    cnt += 1;
	                } else {
	                    cnt = 1;
	                }
	                if (ans < cnt) ans = cnt;
	            }
	            cnt = 1;
	            for (int j=1; j<n; j++) {
	                if (a[j][i] == a[j-1][i]) {
	                    cnt += 1;
	                } else {
	                    cnt = 1;
	                }
	                if (ans < cnt) ans = cnt;
	            }
	        }
	        return ans;
	    }
		
	    public static void main(String[] args) {
	        Scanner sc = new Scanner(System.in);
	        
	        int n = sc.nextInt();
	        char[][] a = new char[n][n];
	        
	        for (int i=0; i<n; i++) {
	            a[i] = sc.next().toCharArray();
	        }
	        
	        int ans = 0;
	        
	        for (int i=0; i<n; i++) {
	            for (int j=0; j<n; j++) {
	                if (j+1 < n) {
	                    char t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t;
	                    int temp = check(a);
	                    if (ans < temp) ans = temp;
	                    t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t;
	                }
	                if (i+1 < n) {
	                    char t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
	                    int temp = check(a);
	                    if (ans < temp) ans = temp;
	                    t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
	                }
	            }
	        }
	        System.out.println(ans);
	}
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/3085