[백준알고리즘] 브루트포스 - 3085번 사탕 게임 문제

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

3085번: 사탕 게임

 

N 크기가 50 이내로, 작은 숫자이기 때문에 브루트포스로 해결 가능한 문제

사탕을 좌우로 바꿨을때 바꾼 가로행의 가장 긴 사탕의 개수를 구하고

해당 세로열 두줄의 가장 긴 사탕개수를 다 구해봤을때 나올 수 있는 가장 긴 연속되는 사탕의 수를 구하는 식의 문제인데

-> X. 뒤에설명

난이도만 봤을때 그리 어려운 단계의 문제도 아닌데 오래걸리고있다

코드가 점점 길어지고..가독성도 떨어지고..이게 맞나 싶고..집중력도 떨어지고..

하...for문 많아지면서 지역변수 i..j..k..등등 남발되는거 싫다 이대로 코드를 짜고 싶지 않다!!

부분부분 함수로 만들걸 그랬다

그래도 일단 끝까지 구현은 했다

 

 

결론은 세번 만에야 맞췄다. 왜 그랬냐면..

시행착오가 꽤 있었는데, 우선 첫번째로 짠 코드는 다음과 같았다.

package baekjoonWeek3;

import java.io.*;

public class CandyGame {    //백준 3085번 사탕 게임 문제
    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());    //NxN 크기의 보드 크기
        char[][] candyBoard = new char[N][N];   //C P Z Y 네가지가 저장
        String str;
        //2차원 배열에 사탕 정보부터 저장
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < N; j++) {
                candyBoard[i][j] = str.charAt(j);
            }
        }

        //가로 방향으로 바꾸는 경우
        char temp;
        int comboRow = 0;  //가장 긴 연속되는 같은 종류 사탕의 길이(행 기준)
        int comboCol = 0;  //가장 긴 연속되는 같은 종류 사탕의 길이(열 기준)
        char candyNow = 'C';  //현재 보고있는 사탕의 종류
        int comboMax = 0;   //가장 긴 길이
        for (int i = 0; i < N; i++) { //총 N행에 대하여 바꿔본다
            for (int j = -1; j < N - 1; j++) {   //마지막 N-1번째 사탕은 오른쪽과 교환x
                //오른쪽과 교환과정
                if(candyBoard[i][j] == candyBoard[i][j + 1]) continue;
                temp = candyBoard[i][j];
                candyBoard[i][j] = candyBoard[i][j + 1];
                candyBoard[i][j + 1] = temp;

                comboRow = 0; 
                //가장 긴 사탕의 길이 구하기(i행)
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[i][k];    //첫 사탕정보 일단 저장
                        comboRow++;    //일단 1개
                    } else {
                        if (candyBoard[i][k] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboRow++;
                            if(comboRow > comboMax) comboMax = comboRow;
                        } else {
                            if(comboRow > comboMax) comboMax = comboRow;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                            comboRow = 1;  //1로 되돌아감
                            candyNow = candyBoard[i][k];    //새로운 사탕정보 등록
                        }
                    }
                }
                comboCol = 0;
                //가장 긴 사탕의 길이 구하기(j열)
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[k][j];    //첫 사탕정보 일단 저장
                        comboCol++;    //일단 1개
                    } else {
                        if (candyBoard[k][j] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboRow++;
                            if(comboCol > comboMax) comboMax = comboCol;
                        } else {
                            if(comboCol > comboMax) comboMax = comboCol;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                            comboCol = 1;  //1로 되돌아감
                            candyNow = candyBoard[k][j];    //새로운 사탕정보 등록
                        }
                    }
                }
                comboCol = 0;
                //가장 긴 사탕의 길이 구하기(j+1열)
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[k][j+1];    //첫 사탕정보 일단 저장
                        comboCol++;    //일단 1개
                    } else {
                        if (candyBoard[k][j+1] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboCol++;
                            if(comboCol > comboMax) comboMax = comboCol;
                        } else {
                            if(comboCol > comboMax) comboMax = comboCol;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                            comboCol = 1;  //1로 되돌아감
                            candyNow = candyBoard[k][j+1];    //새로운 사탕정보 등록
                        }
                    }
                }
                //확인했으면 다시 원위치로 돌려놓는다
                temp = candyBoard[i][j];
                candyBoard[i][j] = candyBoard[i][j + 1];
                candyBoard[i][j + 1] = temp;
            }
        }
        //세로 방향으로 바꾸는 경우
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 1; j++) {
                //아래쪽과 교환과정
                if(candyBoard[j][i] == candyBoard[j + 1][i]) continue;
                temp = candyBoard[j][i];
                candyBoard[j][i] = candyBoard[j + 1][i];
                candyBoard[j + 1][i] = temp;

                //가장 긴 사탕의 길이 구하기(i열)
                comboCol = 0;
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[k][i];    //첫 사탕정보 일단 저장
                        comboCol++;    //일단 1개
                    } else {
                        if (candyBoard[k][i] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboCol++;
                            if (comboCol > comboMax) comboMax = comboCol;
                        } else {
                            if (comboCol > comboMax) comboMax = comboCol;
                            comboCol = 1;  //1로 되돌아감
                            candyNow = candyBoard[k][i];    //새로운 사탕정보 등록
                        }
                    }
                }
                //가장 긴 사탕의 길이 구하기(j행)
                comboRow = 0;
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[j][k];    //첫 사탕정보 일단 저장
                        comboRow++;    //일단 1개
                    } else {
                        if (candyBoard[j][k] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboRow++;
                            if (comboRow > comboMax) comboMax = comboRow;
                        } else {
                            if (comboRow > comboMax) comboMax = comboRow;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                            comboRow = 1;  //1로 되돌아감
                            candyNow = candyBoard[j][k];    //새로운 사탕정보 등록
                        }
                    }
                }
                comboRow = 0;
                //가장 긴 사탕의 길이 구하기(j+1열)
                for (int k = 0; k < N; k++) {
                    if (k == 0) {
                        candyNow = candyBoard[j+1][k]; //첫 사탕정보 일단 저장
                        comboRow++;    //일단 1개
                    } else {
                        if (candyBoard[j+1][k] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                            comboRow++;
                            if (comboRow > comboMax) comboMax = comboRow;
                        } else {
                            if (comboRow > comboMax) comboMax = comboRow;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                            comboRow = 1;  //1로 되돌아감
                            candyNow = candyBoard[j+1][k];    //새로운 사탕정보 등록
                        }
                    }
                }
                //다시 원위치로
                temp = candyBoard[j][i];
                candyBoard[j][i] = candyBoard[j + 1][i];
                candyBoard[j + 1][i] = temp;
            }
        }
        bw.write(Integer.toString(comboMax));
        bw.flush();
        bw.close();
    }
}

 

이런 코드 너무 싫어...짜면서도 극혐이었다 (버리고싶었음)

사탕을 가로 방향으로 바꾸고, 바꾼 두 사탕의 위치의 행에 해당하는 한줄과,

열에 해당되는 두줄 이렇게 총 세줄에서 나올 수 있는 가장 긴 사탕의 길이를 구하고

다음으로는 사탕을 세로 방향으로 바꾸고 바꾼 두 사탕의 위치의 행에 해당되는 두줄과

해당되는 열 한줄 이렇게 세줄에서 나올 수 있는 가장 긴 사탕의 길이를 확인하는 코드였다

그러니까 바꾼 사탕의 위치와 관련한 세줄씩만을 확인하도록 짠 코드였던것이다

그러면 덜 확인해도 되니까 좋겠지~했는데 이게 두번이나 틀렸습니다가 뜨게 한 주범이었다..

문제 게시판에 가서 온갖 반례들을 다 입력해봤는데 다 맞게 나왔었다

그야말로 맞왜틀?????상태였다

구글에 "백준 3085번 맞왜틀"이라고 검색하니까 ㅋㅋㅋ나와 같은 문제를 겪은 사람의 포스팅이 있었고

덕분에 뭐가 문제인지 깨달았다

나는 바꾼 부분만 확인하도록 짰는데..사탕을 바꾸지 않은 부분의 행/열에서 가장 긴 사탕의 길이가 나올수도 있기 때문인것이었다

처음부터 그냥 다 확인하도록 하는 코드를 짤걸 그랬다.

브루트포스로 풀거면 확실하게 브루트포스하게 풀어야겠다고 마음먹었다.(?)맞는 교훈인지는 모르겠지만 ㅎㅎ

 

그리하여 수정한 코드는 다음과 같다

package baekjoonWeek3;

import java.io.*;

public class CandyGame {    //백준 3085번 사탕 게임 문제
    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());    //NxN 크기의 보드 크기
        char[][] candyBoard = new char[N][N];   //C P Z Y 네가지가 저장
        String str;
        //2차원 배열에 사탕 정보부터 저장
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < N; j++) {
                candyBoard[i][j] = str.charAt(j);
            }
        }

        //가로 방향으로 바꾸는 경우
        char temp;
        int comboRow = 0;  //가장 긴 연속되는 같은 종류 사탕의 길이(행 기준)
        int comboCol = 0;  //가장 긴 연속되는 같은 종류 사탕의 길이(열 기준)
        char candyNow = 'C';  //현재 보고있는 사탕의 종류
        int comboMax = 0;   //가장 긴 길이
        for (int i = 0; i < N; i++) { //총 N행에 대하여 바꿔본다
            for (int j = 0; j < N - 1; j++) {   //마지막 N-1번째 사탕은 오른쪽과 교환x
                //오른쪽과 교환과정
                temp = candyBoard[i][j];
                candyBoard[i][j] = candyBoard[i][j + 1];
                candyBoard[i][j + 1] = temp;

                //가장 긴 사탕의 길이 구하기(행)
                for (int k = 0; k < N; k++) {
                    comboRow = 0;
                    for (int h = 0; h < N; h++) {
                        if (h == 0) {
                            candyNow = candyBoard[k][h];    //첫 사탕정보 일단 저장
                            comboRow++;    //일단 1개
                        } else {
                            if (candyBoard[k][h] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                                comboRow++;
                                if(comboRow > comboMax) comboMax = comboRow;
                            } else {
                                if(comboRow > comboMax) comboMax = comboRow;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                                comboRow = 1;  //1로 되돌아감
                                candyNow = candyBoard[k][h];    //새로운 사탕정보 등록
                            }
                        }
                    }
                }

                //가장 긴 사탕의 길이 구하기(열)
                for (int k = 0; k < N; k++) {
                    comboCol = 0;
                    for (int h = 0; h < N; h++) {
                        if (h == 0) {
                            candyNow = candyBoard[h][k];    //첫 사탕정보 일단 저장
                            comboCol++;    //일단 1개
                        } else {
                            if (candyBoard[h][k] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                                comboCol++;
                                if(comboCol > comboMax) comboMax = comboCol;
                            } else {
                                if(comboCol > comboMax) comboMax = comboCol;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                                comboCol= 1;  //1로 되돌아감
                                candyNow = candyBoard[h][k];    //새로운 사탕정보 등록
                            }
                        }
                    }
                }
                //확인했으면 다시 원위치로 돌려놓는다
                temp = candyBoard[i][j];
                candyBoard[i][j] = candyBoard[i][j + 1];
                candyBoard[i][j + 1] = temp;
            }
        }

        //세로 방향으로 바꾸는 경우
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 1; j++) {
                //아래쪽과 교환과정
                if(candyBoard[j][i] == candyBoard[j + 1][i]) continue;
                temp = candyBoard[j][i];
                candyBoard[j][i] = candyBoard[j + 1][i];
                candyBoard[j + 1][i] = temp;

                //가장 긴 사탕의 길이 구하기(행)
                for (int k = 0; k < N; k++) {
                    comboRow = 0;
                    for (int h = 0; h < N; h++) {
                        if (h == 0) {
                            candyNow = candyBoard[k][h];    //첫 사탕정보 일단 저장
                            comboRow++;    //일단 1개
                        } else {
                            if (candyBoard[k][h] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                                comboRow++;
                                if(comboRow > comboMax) comboMax = comboRow;
                            } else {
                                if(comboRow > comboMax) comboMax = comboRow;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                                comboRow = 1;  //1로 되돌아감
                                candyNow = candyBoard[k][h];    //새로운 사탕정보 등록
                            }
                        }
                    }
                }

                //가장 긴 사탕의 길이 구하기(열)
                for (int k = 0; k < N; k++) {
                    comboCol = 0;
                    for (int h = 0; h < N; h++) {
                        if (h == 0) {
                            candyNow = candyBoard[h][k];    //첫 사탕정보 일단 저장
                            comboCol++;    //일단 1개
                        } else {
                            if (candyBoard[h][k] == candyNow) {    //현재위치의 사탕이 이전 저장된 사탕과 같은종류라면
                                comboCol++;
                                if(comboCol > comboMax) comboMax = comboCol;
                            } else {
                                if(comboCol > comboMax) comboMax = comboCol;    //새로 들어가기 전에, 이전 콤보보다 크다면 갱신
                                comboCol = 1;  //1로 되돌아감
                                candyNow = candyBoard[h][k];    //새로운 사탕정보 등록
                            }
                        }
                    }
                }
                //다시 원위치로
                temp = candyBoard[j][i];
                candyBoard[j][i] = candyBoard[j + 1][i];
                candyBoard[j + 1][i] = temp;
            }
        }
        bw.write(Integer.toString(comboMax));
        bw.flush();
        bw.close();
    }
}

 

 

결국 맞긴 했어도 이거보단 더 잘 짜보고싶다.

백준 강의에 있는 코드를 보고 공부해보기로 한다..