[BOJ] 백준 [3085] 사탕게임 JAVA

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

📝문제

📝풀이

탐색 위치를 p1 이라고 하면 x 방향으로 1 또는 y 방향으로 1 다음인 p2 와 자리값을 바꾸고
주어진 2차원 배열을 모두 탐색해서 연속되는 문자의 최대 값을 갱신시키면 된다.

N<=50 이기 때문에 충분히 시간내에 탐색할 수 있다. => lis 알고리즘 사용 x 

import java.io.*;
import java.util.*;

public class Main {

    static int max = 1;
    static int n;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        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++){
            map[i] = br.readLine().toCharArray();
        } // end input

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){

                if(isRange(j+1,i)) {
                    swap(new Point(j,i),new Point(j+1,i));
                }

                if(isRange(j,i+1)) {
                    swap(new Point(j,i),new Point(j,i+1));
                }
            }
        }

        System.out.println(max);
    }

    private static void swap(Point p1,Point p2) {  // 0:x 1:y
        char cur = map[p1.y][p1.x];
        char next = map[p2.y][p2.x];
        // swap
        map[p1.y][p1.x] = next;
        map[p2.y][p2.x] = cur;
        search(); // 연속 되는 사탕 찾기
        // restore
        map[p1.y][p1.x] = cur;
        map[p2.y][p2.x] = next;

    }

    private static void search() {

        int cnt = 1;

        for(int i=0;i<n;i++){ // x 방향 진행
            for(int j=0;j<n;j++){

                if(isRange(j+1,i) && map[i][j]==map[i][j+1]){ // 연속으로 같으면 cnt 수 증가
                    cnt++;
                    max = Math.max(max,cnt);
                }else{
                    cnt=1;
                }
            }
        }

        for(int i=0;i<n;i++){ // y 방향 진행
            for(int j=0;j<n;j++){

                if(isRange(i,j+1) && map[j][i]==map[j+1][i]){
                    cnt++;
                    max = Math.max(max,cnt);
                }else{
                    cnt=1;
                }
            }
        }
    }

    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<n&&y<n;
    }
    static class Point{
        int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}​