백준-3085번/사탕 게임 (java)

 

 

문제 이해

 

N x N의 문자 배열에서 임의의 한 점을 인점한 배열의 요소와 교환한 후 연속된 문자의 최대값을 출력하면 된다.(애니팡과 유사)

 

 

문제 해결

 

순서

교환 --> 최대 연속 찾기  이것을 반복하면 된다.

 

 

우선 인접한 요소와 교환을 해야 하므로 swap 함수를 만들어 준다.

<Swap 함수>

 public static void swap(int x,int y, int a , int b){
        char tmp=arr[x][y];
        arr[x][y]=arr[a][b];
        arr[a][b]=tmp;
    }

 

 

 

교환을 했을때의 최대 연속을 찾아주는 search 함수를 만들어준다.

<Search 함수>

public static void search(){
        //행마다 비교
        for(int i=0; i<N; i++){
            int count =1;

            //옆이랑 비교
            for(int j=0; j<N-1; j++){
                if(arr[i][j]==arr[i][j+1]){
                    count++;
                    max=Math.max(count,max);
                }
                else{
                    count=1;
                }
            }
        }

        //열마다 비교
        for(int i=0; i<N; i++){
            int count=1;
            for(int j=0; j<N-1; j++){
                if(arr[j][i]==arr[j+1][i]){
                    count++;
                    max=Math.max(count,max);
                }
                else{
                    count=1;
                }
            }
        }
    }

 

* 열을 기준으로 비교할때는 선택된 점의 오른쪽 요소와 비교를 한다.

O-->	--->	-->

* 행을 기준으로 비교할때는 선택된 점의 아래 요소와 비교를 한다.

O
|
|

 

 

 

 

메인함수에서 swap함수와 search함수를 이용해서 나올수 있는 모든 경우의 수를 비교한다.

//행을 기준으로 오른쪽과 비교
for(int i=0; i<N; i++){
    for(int j=0; j<N-1; j++){
        swap(i,j,i,j+1);
        search();
        swap(i,j+1,i,j);
    }
}

//열 기준으로 아래와 비교
for(int i=0; i<N-1; i++){
    for(int j=0; j<N; j++){
        swap(i,j,i+1,j);
        search();
        swap(i+1,j,i,j);
    }
}

 

행을 기준으로 할때는 swap을 오른쪽 요소와 한 경우이고, 열을 기준으로 할때는 아래 요소와 한 경우이다.

 

<전체 코드>

import java.util.Scanner;

public class Problem3085 {
    static char[][] arr;
    static int N;
    static int max=1;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        arr=new char[N][N];

        for(int i=0; i<N; i++){
            String s=scanner.next();
            for(int j=0; j<N; j++){
                arr[i][j]=s.charAt(j);
            }
        }
        //행을 기준으로 오른쪽과 비교
        for(int i=0; i<N; i++){
            for(int j=0; j<N-1; j++){
                swap(i,j,i,j+1);
                search();
                swap(i,j+1,i,j);
            }
        }

        //열 기준으로 아래와 비교
        for(int i=0; i<N-1; i++){
            for(int j=0; j<N; j++){
                swap(i,j,i+1,j);
                search();
                swap(i+1,j,i,j);
            }
        }
        System.out.println(max);

    }

    public static void swap(int x,int y, int a , int b){
        char tmp=arr[x][y];
        arr[x][y]=arr[a][b];
        arr[a][b]=tmp;
    }

    public static void search(){
        //행마다 비교
        for(int i=0; i<N; i++){
            int count =1;

            //옆이랑 비교
            for(int j=0; j<N-1; j++){
                if(arr[i][j]==arr[i][j+1]){
                    count++;
                    max=Math.max(count,max);
                }
                else{
                    count=1;
                }
            }
        }

        //열마다 비교
        for(int i=0; i<N; i++){
            int count=1;
            for(int j=0; j<N-1; j++){
                if(arr[j][i]==arr[j+1][i]){
                    count++;
                    max=Math.max(count,max);
                }
                else{
                    count=1;
                }
            }
        }
    }

}

 

 

 

어려웠던 점 : 아래 요소, 오른쪽 요소와는 교환을 하는데 왼쪽이나 위 요소와는 교환을 안하는 이유 ==> 아래, 오른쪽 요소와 교환을 했을때 다 확인이 된 경우이기 때문에 다시 하지 않는다.