[알고리즘 PS] 백준 3085번 사탕 게임 자바 문제풀이

문제

해당 포스팅은 백준의 3085번 사탕 게임 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

문제를 보고 우리가 먼저 해야할 일은 무엇일까?

 

바로 경우의 수에 따른 시간 복잡도 계산이다.

 

이 시간복잡도가 어떻게 나오고 통과를 하냐 마냐에 따라서 사용할 수 있는 알고리즘의 폭이 다양해진다.

 

이번 문제에서는 2개의 조건을 생각해서 보면 된다.

1. 인접한 칸의 두 원소를 교환한다.
2. 가장 긴 연속 부분 행,열을 고른 다음 먹는다.

인접한 칸의 두 원소를 교환한다.

n x n 행렬에서 모든 원소가 인접한 칸을 고를 경우의 수는 얼마나 될까?

 

아마 4 * n^2이 될 것이다.

 

하지만 생각을 해보면 2 * n^2으로 줄일 수 있다.

왜냐하면 임의의 한 칸에서는 그 전 칸에서 교환을 했던 과거가 있기 때문에

• 이전의 왼쪽에서 교환된 경우
• 이전의 위에서 교환된 경우

를 제외하면 2 * n^2이 될 것이다.

가장 긴 연속 부분 행,열을 고른 다음 먹는다.

가장 긴 연속 부분 행, 열을 선택하는 경우는 한 원소가 교환된 후 해당 원소의 행과 열을 검사하는 로직으로 또한 2 * n^2이 소요된다.

 

그럼 이 둘을 모두 합했을 때, 4 * n^2 이므로 우리의 N이 최악의 경우 50이라면 총 2500^2번 수행하게 된다.

어떤 알고리즘을 써야할지 나왔다.

n에 대해 모든 경우가 충분히 작은 관계로 우리는 완전 탐색 알고리즘을 사용할 수 있다.

오답 후보

정답 코드

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());

        char[][] board = new char[n][n];
        int answer = 0;

        int[] dx = {0, 1};
        int[] dy = {1, 0};

        for (int i = 0; i < n; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                board[i][j] = line[j];
            }
        }


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

                if(j + 1 < n){
                    swap(board, j, j + 1, i, i);
                    answer = Math.max(answer, countCandy(board));
                    swap(board, j, j + 1, i, i);
                }
                if(i + 1 < n) {
                    swap(board, j, j, i, i + 1);
                    answer = Math.max(answer, countCandy(board));
                    swap(board, j, j, i, i + 1);
                }

            }
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    private static int countCandy(char[][] arr) {
        int count = 1;

        for (int i = 0; i < arr.length; i++) {
            int temp = 1;
            for (int j = 1; j < arr.length; j++) {
                if(arr[i][j] == arr[i][j-1]) {
                    temp++;
                }
                else temp = 1;
                count = Math.max(count, temp);
            }
        }

        for (int i = 0; i < arr.length; i++) {
            int temp = 1;
            for (int j = 1; j < arr.length; j++) {
                if(arr[j][i] == arr[j-1][i]) {
                    temp++;
                }
                else temp = 1;
                count = Math.max(count, temp);
            }
        }
        return count;
    }

    private static void swap(char[][] arr, int x1, int x2, int y1, int y2) {
        char temp = arr[y1][x1];
        arr[y1][x1] = arr[y2][x2];
        arr[y2][x2] = temp;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.