[BOJ] 3085 사탕 게임

사탕 게임

풀이

• N*N 칸의 보드가 주어지고, C,P,Z,Y로 채워져있다.
• 사탕의 색이 다른 인접한 두 칸을 고르고, swap한 뒤 , 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고르고 사탕을 지운다
• 지울 수 있는 사탕의 최대 수를 구해라.
• 완전탐색이니까 진짜 그냥 다 봤다. 2중 for 문 돌리면서 사방탐색으로 자리 바꿔본 뒤,현재 내가 있는 열과 행에서 같은 색으로 이루어져 있는 가장 긴 연속 부분을 찾았다.
• 다 돌고난 뒤, 보드를 처음 상태로 돌려주고 전체 사탕에 대해 반복

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int answer = Integer.MIN_VALUE;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int N;
    static char[][] map;
    public static void main(String[] args) throws Exception {
        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++){
            String str = br.readLine();
            for(int j=0;j<N;j++){
                map[i][j] = str.charAt(j);
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                check(i,j);
            }
        }
        if(answer ==Integer.MIN_VALUE) System.out.println(0);
        else System.out.println(answer);
    }
    static void check(int i, int j){
        for(int m=0;m<4;m++){
            int nx = i+dx[m];
            int ny = j+dy[m];
            if(nx>=0 && nx<N && ny>=0 && ny<N){
                char origin = map[i][j];
                char next = map[nx][ny];
                map[i][j] = next;
                map[nx][ny] = origin;
                int rowCnt = 1;
                int colCnt = 1;
                for(int l=0;l<N-1;l++){
                    for(int t=l+1;t<N;t++){
                        if(map[i][l]==map[i][t]){
                            rowCnt++;
                        }
                        else{
                            break;
                        }
                    }
                    for(int t=l+1;t<N;t++){
                        if(map[l][j]==map[t][j]){
                            colCnt++;
                        }
                        else{
                            break;
                        }
                    }
                    answer = Math.max(answer,Math.max(rowCnt,colCnt));
                    rowCnt = 1;
                    colCnt = 1;
                }
                map[i][j] = origin;
                map[nx][ny] = next;
            }
        }
    }
  }

• 4방으로 할 필요 없고, 오른쪽, 아래쪽으로 인접한 애들만 비교해줘도 됨.