'Do it 자료구조와 함께 배우는 알고리즘 입문' 도서를 토대로 공부하고 관련한 문제를 찾아풀어보고 있습니다.

'브루트 포스' 알고리즘 문제 풀이입니다!!!

문제

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

[나의 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static char [][] board;
    static int N;
    static int max=0;

    static void check(){
        
        // 가로 체크
        for(int i=0; i<N; i++){
            int cnt = 1;
            for (int j=0; j<N-1; j++){
                if (board[i][j] == board[i][j+1]){
                    cnt ++;
                }
                else{
                    cnt = 1;
                }
                max = Math.max(max,cnt);

            }
        }

        // 세로 체크
        for (int i=0; i<N; i++){
            int cnt = 1;
            for (int j=0; j<N-1; j++){

                if (board[j][i] == board[j+1][i]){
                    cnt++;
                }
                else{
                    cnt = 1;
                }
                max = Math.max(max,cnt);
            }

        }
    }



    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        board = new char [N][N];

        for (int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0;j<N;j++){
                board[i][j] = line.charAt(j);
            }
        }

        // 가로 먼저 체크
        for (int i=0; i<N; i++){
            for (int j=0; j<N-1; j++){

                // 가로 인접 문자 교환
                char tmp = board[i][j];
                board[i][j] = board[i][j+1];
                board[i][j+1] = tmp;

                // 최대 갯수 확인

                check();

                // 교환한 문자 복구
                board[i][j+1] = board[i][j];
                board[i][j] = tmp;

            }
        }

        // 세로 체크
        for (int i=0; i<N; i++){
            for (int j=0; j<N-1; j++){

                // 가로 인접 문자 교환
                char tmp = board[j][i];
                board[j][i] = board[j+1][i];
                board[j+1][i] = tmp;

                // 최대 갯수 확인

                check();

                // 교환한 문자 복구
                board[j+1][i] = board[j][i];
                board[j][i] = tmp;

            }
        }

        bw.write(max+"");
        bw.flush();
    }
}

가능한 모든 경우의 수를 나열하며 찾아가는 완전 탐색 문제입니다. 문제 해결 방안 아이디어를 떠올리는데는 어렵지 않았지만 직접 구현하는 과정에 있어 코드가 길어지고 수정하기 힘들어지면서 문제 해결에 이틀 정도 소모하였습니다.
😥😥😥

또한 문제 풀이후 다른 풀이들과 비교했을 때 static 변수를 통한 변수 재사용성을 늘린 코드들을 보고 조금 더 효율적인 코드로 수정했습니다. 💁‍♂️💁‍♂️💁‍♂️

이번 문제는 직접 구현하는 과정에 있어 몇시간 동안 고민하면서 심리적으로 많이 지친 문제였습니다. 브루트 포스 문제는 for문만 잘 사용하면 쉬운 알고리즘이라고 생각하였는데 조건이 여러개 일 수록 디버깅하는데 어려워었습니다. 브루트 포스 문제는 이후에 다시 한번 도전해보도록하겠습니다.🐏🐏🐏

감사합니다.