BOJ_3085 : 사탕 게임

👉 문제링크

3085번: 사탕 게임

---

---

🔸 문제 분석 🔸

• n X n 로 사탕이 있다.
  • 사탕의 종류는 C, P, Z, Y가 있다.
  • 인접한 두 칸을 골라 사탕을 교환한다.
  • 같은 색으로 이루어진 행 또는 열 중 먹을 수 있는 사탕의 최대값을 출력한다.
• 풀이
  • 최대값을 찾기 위해서는 교환할 수 있는 모든 경우의 수를 찾아야 한다.
    • 사탕 교환은 아래 혹은 오른쪽으로만 이동하며 진행한다.
    • 각각의 경우에 나오는 연속된 사탕의 최대값을 저장한다.
    • 사탕의 최소값은 1이다.
  • 최대값을 출력한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    static char[][] arr;

    private static int countCandy(int n, int i, int j, int order, int max) {
        char[][] candyes = new char[n][n];

        for (int k = 0; k < n; k++) { // 2중 반복문
            for (int l = 0; l < n; l++) {
                candyes[k][l] = arr[k][l];
            }
        }

        if (order == 0) {
            char temp = candyes[i][j];
            candyes[i][j] = candyes[i + 1][j];
            candyes[i + 1][j] = temp;
        } else {
            char temp = candyes[i][j];
            candyes[i][j] = candyes[i][j + 1];
            candyes[i][j + 1] = temp;
        }

        for (int k = 0; k < n; k++) {
            int count = 1;
            for (int l = 1; l < n; l++) {
                if (candyes[k][l] == candyes[k][l - 1]) {
                    count++;
                } else {
                    if (count > max) {
                        max = count;
                    }
                    count = 1;
                }
            }
            if (count > max) {
                max = count;
            }
        }

        for (int k = 0; k < n; k++) {
            int count = 1;
            for (int l = 1; l < n; l++) {
                if (candyes[l][k] == candyes[l - 1][k]) {
                    count++;
                } else {
                    if (count > max) {
                        max = count;
                    }
                    count = 1;
                }
            }
            if (count > max) {
                max = count;
            }
        }

        return max;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            String string = sc.next();
            for (int j = 0; j < n; j++) {
                arr[i][j] = string.charAt(j);
            }
        }

        int answer = 1;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                answer = countCandy(n, i, j, 0, answer);
            }
        }

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

 

🔸 코드 해석 🔸

• main 메소드에서 n X n 사탕을 입력받아 char형 이차원 배열 arr에 저장한다.
  • 아래쪽 사탕과 교환할 때는 행을 n-1개 탐색한다.
  • 오른쪽 사탕과 교환할 때는 열을 n-1개 탐색한다.
• countCandy 메소드에서 연속된 사탕의 최대값을 반환한다.
  
  • arr를 candyes 배열에 복사한다.
  • order가 0이면 아래쪽, 아니라면 오른쪽과 사탕을 교환한다.
  • 한 행에서 가장 긴 연속 사탕의 수를 확인해 answer와 비교한다.
  • 한 열에서 가장 긴 연속 사탕의 수를 확인해 answer와 비교한다.
• answer를 출력한다.

---

🔸 end 🔸

• 처음부터 풀이와 같은 접근 방법을 생각했지만, 시간초과가 걱정됐는데 부르트포스 태그를 보고 믿음을 가졌다.
• countCandy 메소드에서 행과 열의 가장 긴 연속 사탕의 수를 찾는 for문에서 max값을 저장하는 코드를 빠뜨려서 1회 틀렸다.
  • 이중 for문에서 안쪽 for문이 끝나야 count를 max와 비교했었는데, 비교하는 사탕이 서로 다를 때에도 max와 비교해서 저장해야했다.
  • 결과적으로 max비교문이 2번씩 들어가야한다.