사탕 게임

📍 문제 설명

 

💡 접근

사탕의 색이 다른 부분을 교환시켜서 긴 부분을 구하면 되는 문제

인접한 두칸이라고 했으므로 북동 쪽만 확인해줘도 되고 그냥 4 방향 중복으로 봐도 된다.

 

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer, cnt;
    static String a, t;
    static char[][] board,clone;
    static boolean[][] visited;
    static int[] histogram;
    static int[] dx = {-1, 0, 1, 0,}; //북동남서
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        kb.nextLine();
        board = new char[n][n];
        for(int i = 0; i < n; i++) {
            String s = kb.nextLine();
            for(int j = 0; j < n; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                T.solution(i, j);
            }
        }
        System.out.println(answer);


    }

    private void solution(int x, int y) {
        //현재 좌표에서 인접하고 색이 다른 칸 찾기
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n || board[x][y] == board[nx][ny]) continue;
            //사탕 교환하기
            char tmp = board[x][y];
            board[x][y] = board[nx][ny];
            board[nx][ny] = tmp;

            eatting_candy();
            //사탕 제자리로
            tmp = board[nx][ny];
            board[nx][ny] = board[x][y];
            board[x][y] = tmp;
        }
    }

    private void eatting_candy() {
        for(int i = 0; i < n; i++) {
            cnt = 1;
            for(int j = 0; j < n-1; j++) {
                if(board[i][j] == board[i][j+1]) cnt++;
                else cnt = 1;
                answer = Math.max(answer, cnt);
            }
        }
        for(int i = 0; i < n; i++) {
            cnt = 1;
            for(int j = 0; j < n-1; j++) {
                if(board[j][i] == board[j+1][i]) cnt++;
                else cnt = 1;
                answer = Math.max(answer, cnt);
            }
        }
    }

}