[백준/java] 3085번 사탕게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

• 분류 : 완전탐색

 

 

처음에 풀고나서 다른 사람들 풀이를 보고 기존에 제출했던 내 코드를 많이 뜯어고쳤다.

아래는 내가 처음 제출한 코드이다.

 

첫번째 풀이

• 반복문을 돌면서 swap()메서드로 인접한 사탕 위치(상하좌우)를 서로 바꿔서 clone된(swap된 배열) 배열을 리턴해준다. 그리고 그 swap된 배열을 countMaxCandyCount() 메서드로 행과 열을 체크하여 각 행과 열에 최대 사탕 개수를 찾는다.

import java.util.Scanner;

public class BOJ3085 {
    static char[][] arr;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //  (3 ≤ N ≤ 50)
        sc.nextLine();
        arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++) {
                arr[i][j] = s.charAt(j);
            }
        }
        findMax();
    }

    static private void findMax() {
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //인접한 사탕 swap
                max = Math.max(countMaxCandyCount(swap(i, j, i, j - 1)), max);
                max = Math.max(countMaxCandyCount(swap(i, j, i, j + 1)), max);
                max = Math.max(countMaxCandyCount(swap(i, j, i + 1, j)), max);
                max = Math.max(countMaxCandyCount(swap(i, j, i - 1, j)), max);

            }
        }
        System.out.println(max);
    }

    static int countMaxCandyCount(char[][] clone) {
        if (clone == null) return -1;
        int max = 0;
        // row 체크
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n - 1; j++) {
                if (clone[i][j] == clone[i][j + 1]) count++;
                else count = 1;
                max = Math.max(max, count);
            }
        }

        // column 체크
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n-1; j++) {
                if (clone[j][i] == clone[j + 1][i]) count++;
                else count = 1;
                max = Math.max(max, count);
            }
        }
        return max;
    }

    static private char[][] swap(int i, int j, int a, int b) {
				//가장자리라서 상하좌우 위치가 유효하지 않은 경우
        if (a < 0 || a > n - 1 || b < 0 || b > n - 1) {
            return null;
        }
        // deep copy
        char[][] clone = new char[n][n];
        for(int x = 0; x<n; x++) {
            clone[x] = arr[x].clone();
        }

			  //swap 
        char tmp = clone[i][j];
        clone[i][j] = clone[a][b];
        clone[a][b] = tmp;

        return clone;
    }
}

 

수정한 코드

코드가 좀 지저분함을 스스로 느꼈다. 일단 굳이 swap한 배열을 clone해야하나? 싶기도 했고, 여러모로 리팩토링이 필요했다. 다른 사람들의 풀이를 참고해서 기존 코드를 아래와 같이 수정했다.

 

1. 상하좌우를 전체 다 swap하지 않고, 오른쪽과 아래쪽 값하고만 swap하도록 한다.

• 중복되는 swap 횟수를 줄였다. 어차피 arr[i][j-1]가 오른쪽에 있는 arr[i][j]와 swap하는 것과 arr[i][j]가 왼쪽에 있는 arr[i][j-1]와 swap하는게 동일하기 때문이다. 

2. swap할 때 굳이 deep copy를 해서 배열을 리턴하기보다는, swap 후 다시 원상복구해서 돌려놓는다. 그러면 매개변수로 굳이 배열을 넘길 필요가 없다.

• 위에서 언급했던 배열을 copy하는 부분을 제거했다. 배열을 복사하지 않고 swap후에 다시 되돌려놓으면(다시 swap해주면) 굳이 copy할 필요가 없기 때문이다.

import java.util.Scanner;

public class BOJ3085 {
    static char[][] arr;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //  (3 ≤ N ≤ 50)
        sc.nextLine();
        arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++) {
                arr[i][j] = s.charAt(j);
            }
        }
        findMax();
    }

    static private void findMax() {
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                // 인접한 사탕(오른쪽과 아래쪽) swap
                swap(i, j, i, j + 1);
                max = Math.max(findMaxCandyCount(), max);
                swap(i, j + 1, i, j); //swap했던걸 돌려놓음
            }
        }

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                swap(i, j, i + 1, j);
                max = Math.max(findMaxCandyCount(), max);
                swap(i + 1, j, i, j);
            }
        }
        System.out.println(max);
    }

    static int findMaxCandyCount() {
        int max = 0;
        for (int i = 0; i < n; i++) {
            // row 체크
            int count = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[i][j] == arr[i][j + 1]) count++;
                else count = 1;
                max = Math.max(max, count);
            }

            // column 체크
            count = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[j][i] == arr[j + 1][i]) count++;
                else count = 1;
                max = Math.max(max, count);
            }
        }
        return max;
    }

    static private void swap(int i, int j, int a, int b) {
        char tmp = arr[i][j];
        arr[i][j] = arr[a][b];
        arr[a][b] = tmp;
    }
}