[ 백준 - 3085 ] 사탕게임

난이도 : S2

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

Tag : 구현

 

문제 탐색하기 

- 한줄에 가장많은 사탕의 개수를 계산하는 것이 목표이다.

- 다른점은, 한번 서로 인접한 사탕의 개수를 이동시킨 후 가장 많은 한줄에 가장많은 사탕의 개수를 만들어야한다는 것이다.

(LIKE 애니팡)

시도 1 ( 성공 😲)

떠오른 문제 해결 방법

주목해야할 부분은 한번만 이동한 다는 것이었습니다. 그렇기 때문에 기존에 최대 길이 사탕줄보다 2개 적은 열은 절대 최대열이 되지 못하지 않을까 했지만 000X000 이라고 했을때 X만 바꾸게되면 한번 교체만으로 7개가 되어버립니다. 잘못된 생각이었습니다.

그렇다면 모든 경우의 수를 다 고려한다면? 모든 사탕을 탐색한다고 했을때 N은 최대이므로 50. 50*50= 2500. 4방향으로 교체하는 경우의 수가 있기 때문에 2500*4 = 10,000.여기에 해당 행과 열의 길이를 탐색해야한다면 최대 50*2 = 100

정리하자면 2500*4*100 = 1,000,000 으로 시간내에 가능할 것입니다.

그리고 더 생각해보자면 4방향으로 교체한다면 매번 중복이 발생하였습니다. 

어느 방향으로 교체하든 결과과 동일하기 때문입니다. 그렇기 때문에 사실항 모든 점은 오른쪽, 아래쪽 교체만 확인한다면 모든 경우를 계산할 수 있었습니다.

하지만 이미 시간내에 해결이 가능하고 구현의 복잡도가 높아지기 때문에 이는 생략하였습니다. 

 

 

 

 

 

시간복잡도⏰

전체 칸을 모두 탐색하더라고 

50*50 = 모든 칸

4 = 확인하는 방향

50 * 2 = 해당 칸이 포함된 행과열의 최대 길이 계산

2500*4*100 = 1,000,000

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받습니다.

2. 모든 칸을 탐색하며 4방향으로 교체를 진행합니다.

2-1. 같은 색일 경우 곧바로 다른 방향을 진행합니다.

2-2. 교체를 합니다.

2-3. 행과 열의 최대 길이를 계산합니다.

2-4. 원래 상태로 다시 교체합니다.

 

전체코드

import java.io.IOException;
import java.util.*;

class Main {

    private static final int[] dirR = { 1, 0, -1, 0 };
    private static final int[] dirC = { 0, 1, 0, -1 };
    private static int n;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        char[][] board = new char[n][n];
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            board[i] = s.toCharArray();
        }

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                // 굳이 안바꾸는게 더 길수도 있음.
                int length = maxCalcurateLength(board, r, c);
                if (maxLength < length) {
                    maxLength = length;
                }

                for (int dir = 0; dir < 4; dir++) {
                    int nextR = r + dirR[dir];
                    int nextC = c + dirC[dir];

                    // 벗어나는지 확인
                    if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= n)
                        continue;

                    // 같은 색이면 굳이 교체 X
                    if (board[nextR][nextC] == board[r][c])
                        continue;

                    // 교환
                    char tmp = board[r][c];
                    board[r][c] = board[nextR][nextC];
                    board[nextR][nextC] = tmp;
                    length = maxCalcurateLength(board, r, c);
                    if (maxLength < length) {
                        maxLength = length;
                    }

                    // 다시 교환(원상태로 복귀)
                    tmp = board[r][c];
                    board[r][c] = board[nextR][nextC];
                    board[nextR][nextC] = tmp;
                }
            }
        }
        System.out.println(maxLength);
    }

    public static int maxCalcurateLength(char[][] board, int r, int c) {

        int maxLength = 0;
        int length = 1;

        char previous = board[r][0];
        for (int i = 1; i < n; i++) {
            if (board[r][i] == previous) {
                length++;
            } else {
                if (maxLength < length) {
                    maxLength = length;
                }
                previous = board[r][i];
                length = 1;
            }
        }
        if (maxLength < length) {
            maxLength = length;
        }

        previous = board[0][c];
        length = 1;
        for (int i = 1; i < n; i++) {
            if (board[i][c] == previous) {
                length++;
            } else {
                if (maxLength < length) {
                    maxLength = length;
                }
                previous = board[i][c];
                length = 1;
            }
        }
        if (maxLength < length) {
            maxLength = length;
        }

        return maxLength;
    }
}

 

 

생각지 못했던 것은 굳이 바꾸지 않는것이 최대 길이 일수도있었다는 것이었습니다. 그렇기 때문에 해당 점을 교체하기 전에 길이를 계산해주는로직을 추가하였습니다. (이떄문에 예제 케이스 2를 틀렸었습니다.)

 

마무리

예제 케이스 2번같은 경우를 테스트 케이스로 주어지지 않더라고 스스로 생각할 수 있는 사고력을 길러야할 것 같습니다.

또한  알고리즘 테스트에서는 예쁜 코드 더 효율적이기보다는 내가 작성하기 쉬운코드, 이해하기 쉬운 코드, 시간내에 해결이 가능하다면 빠르게 푸는 것이 중요한 것 같습니다.