'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문만 잘 사용하면 쉬운 알고리즘이라고 생각하였는데 조건이 여러개 일 수록 디버깅하는데 어려워었습니다. 브루트 포스 문제는 이후에 다시 한번 도전해보도록하겠습니다.🐏🐏🐏
감사합니다.