백준: 사탕 게임

본 풀이는 java 언어를 사용하였습니다.
3085번: 사탕 게임

풀이

아래처럼 보드의 각 칸마다 해당 칸의 사탕을 상, 하, 좌, 우 움직이면서 다른 사탕과 바꾼 후
바꿀 때마다 행, 열의 연속된 사탕 최대 개수를 구하면서 그 중에 가장 큰 개수를 구하면 풀 수 있을 것 같았다.
(완전 탐색)

먼저, 사탕을 움직이기 전에 현재 보드에 있는 행, 열의 연속된 최대 사탕 개수를 구한다.
해당 로직은 checkMaxCountOfCandyToEat() 메서드로 분리한다.

public int solution(String[][] board, int n) {
    int maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n);
}

행, 열의 연속된 최대 사탕 개수는 아래와 같이 구할 수 있다.
먼저 행의 연속된 최대 사탕 개수을 구해보자.

private int checkMaxCountOfCandyToEat(String[][] board, int n) {
    int maxCount = 0;

    // 행 체크
    for (int i = 0; i < n; i++) {
        int maxCountOfLineSameColor = 0;
        int countOfLineSameColor = 1;

        for (int j = 1; j < n; j++) {
            String preColor = board[i][j - 1];
            String currentColor = board[i][j];

            if (preColor.equals(currentColor)) {
                countOfLineSameColor++;
            } else {
                maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
                countOfLineSameColor = 1;
            }
        }
        maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
        maxCount = Math.max(maxCount, maxCountOfLineSameColor);
    }
...
}

그리고 열의 연속된 최대 사탕 개수도 체크해준다.

...
// 열 체크
for (int i = 0; i < n; i++) {
    int maxCountOfLineSameColor = 0;
    int countOfLineSameColor = 1;

    for (int j = 1; j < n; j++) {
        String preColor = board[j - 1][i];
        String currentColor = board[j][i];

        if (preColor.equals(currentColor)) {
            countOfLineSameColor++;
        } else {
            maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
            countOfLineSameColor = 1;
        }
    }
    maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
    maxCount = Math.max(maxCount, maxCountOfLineSameColor);
}

return Math.max(maxCountOfCandyToEat, maxCount);

현재 보드에 있는 행, 열의 연속된 최대 사탕 개수를 구했으면,
이제 상, 하, 좌, 우 로 해당 위치의 사탕을 바꾸면서 개수를 체크하면 된다.
상, 하, 좌, 우 로 체크하기 위해 아래와 같이 final int 배열을 만들어준다.

// 상, 하, 좌, 우
private static final int[] X_DIR = {-1, 1, 0, 0};
private static final int[] Y_DIR = {0, 0, -1, 1};

그 후 아래와 같이 해당 위치의 사탕을 바꾼다.

for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        for (int k = 0; k < 4; k++) {
            int nextX = X_DIR[k] + i;
            int nextY = Y_DIR[k] + j;

            // 범위 체크
            if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length) {
                continue;
            }

            swapColor(board, i, j, nextX, nextY);
            maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n);
            swapColor(board, nextX, nextY, i, j);
        }
    }
}

• 범위 체크 부분은 상, 하, 좌, 우 의 사탕을 바꿀 때 배열 밖으로 조회하면 에러 (IndexOutOf)가 발생하는 부분을 막기위해 추가했다.

위 코드에서 추가 설명을 하자면 아래와 같다.

swapColor(board, i, j, nextX, nextY); // 1
maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n); // 2
swapColor(board, nextX, nextY, i, j); // 3

1. 사탕의 위치를 변경한다.
2. 변경 된 사탕의 행, 열의 연속된 최대 사탕 개수를 구한다. (위에서 메서드로 만들었던 부분을 재사용)
3. 다시 사탕의 위치를 원복한다.

swap 은 아래와 같이 처리했다.

private void swapColor(String[][] board, int originX, int originY, int targetX, int targetY) {
    String temp = board[originX][originY];
    board[originX][originY] = board[targetX][targetY];
    board[targetX][targetY] = temp;
}

전체 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[][] board = new String[n][n];
        for (int i = 0; i < board.length; i++) {
            board[i] = br.readLine().split("");
        }

        bw.write(String.valueOf(new Solution().solution(board, n)));
        bw.newLine();

        bw.flush();

        bw.close();
        br.close();
    }
}

class Solution {
    // 상 하 좌 우
    private static final int[] X_DIR = {-1, 1, 0, 0};
    private static final int[] Y_DIR = {0, 0, -1, 1};
    private int maxCountOfCandyToEat;

    public int solution(String[][] board, int n) {
        maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                for (int k = 0; k < 4; k++) {
                    int nextX = X_DIR[k] + i;
                    int nextY = Y_DIR[k] + j;

                    // 범위 체크
                    if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length) {
                        continue;
                    }

                    swapColor(board, i, j, nextX, nextY);
                    maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n);
                    swapColor(board, nextX, nextY, i, j);
                }
            }
        }

        return maxCountOfCandyToEat;
    }

    private void swapColor(String[][] board, int originX, int originY, int targetX, int targetY) {
        String temp = board[originX][originY];
        board[originX][originY] = board[targetX][targetY];
        board[targetX][targetY] = temp;
    }

    private int checkMaxCountOfCandyToEat(String[][] board, int n) {
        int maxCount = 0;

        // 행 체크
        for (int i = 0; i < n; i++) {
            int maxCountOfLineSameColor = 0;
            int countOfLineSameColor = 1;

            for (int j = 1; j < n; j++) {
                String preColor = board[i][j - 1];
                String currentColor = board[i][j];

                if (preColor.equals(currentColor)) {
                    countOfLineSameColor++;
                } else {
                    maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
                    countOfLineSameColor = 1;
                }
            }
            maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
            maxCount = Math.max(maxCount, maxCountOfLineSameColor);
        }

        // 열 체크
        for (int i = 0; i < n; i++) {
            int maxCountOfLineSameColor = 0;
            int countOfLineSameColor = 1;

            for (int j = 1; j < n; j++) {
                String preColor = board[j - 1][i];
                String currentColor = board[j][i];

                if (preColor.equals(currentColor)) {
                    countOfLineSameColor++;
                } else {
                    maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
                    countOfLineSameColor = 1;
                }
            }
            maxCountOfLineSameColor = Math.max(maxCountOfLineSameColor, countOfLineSameColor);
            maxCount = Math.max(maxCount, maxCountOfLineSameColor);
        }

        return Math.max(maxCountOfCandyToEat, maxCount);
    }
}