[백준/Java] 1018_체스판 다시 칠하기 (1) / OutOfIndexError

Brute Force 알고리즘을 활용하는데 교과서 같은 문제! 바로 번갈아 가면서 O, X 칠하기다.

 

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

1018번: 체스판 다시 칠하기

한 번도 해당문제를 진지하게 접한적이 없어 이번 기회에 그 뿌리를 뽑아버리고자 한다. 😊

 

아직 통과하지 못했다는게 함정(!)이지만 일단 어느정도는 된 것 같아 그 기록을 남겨보고자 한다.

 

 

 

 

문제

주어지는 형태는 첫 줄에 가로, 세로의 길이.

 

그리고 다음 줄 부터 흰색인지 검은색인지에 대한 색깔정보가 주어진다.

 

4 4
WWWW
BBBB
WWWW
BBBB

예를 들어 위와 같이 정보가 주어진다면 아래와 같은 체스판의 느낌이 된다.

 

 

 

 

 

그럼 몇개의 체스 판을 다시 칠해야 흰검흰검 혹은 검흰검흰 모양으로 바꿀 수 있는지 알아내면 된다.

 

이 문제는 몇개가 주어지든 8X8 모양의 체스판을 기준으로 생각해야 한다.

 

 

만약 문제가 위와 같이 나왔다면 첫번째 줄에 2개, 두번째 줄에 2개, 세번째 줄에 2개 그리고 마지막으로 네번째 줄에 2개를 칠하면 되므로 총 8개의 체스판을 다시 칠해야 한다.

 

 

 

 

접근방향

해당하는 문제를 해결하기 위해서 일단 배열을 이용해야 겠다고 생각했다.

 

2차원 배열이 아닌 1차원 배열을 이용해서 메모리 사용량을 줄이고 실행시간을 단축시키겠다는 꼼수!를 부릴 생각이였다

 

 

 

 

 

그리고 패턴은 총 두 종류 이므로 두 가지 경우를 계산해서 둘 중 작은 수를 후보군으로 올리겠다고 생각했다.

 

왜 두 종류라고 하나면 1차원 배열로 생각했을때

 

검 흰 검 흰 검 흰 ...

 

이거나

 

흰 검 흰 검 흰 검 ...

 

이기 때문에 두 가지 경우만 생각하면 된다고 생각하고 있다. (오늘 수정하면서 어떻게 생각이 바뀔지 모름 ㅎ)

 

 

 

 

이렇게 되면 조건이 하나 생긴다.

 

 

인덱스가 0부터 시작한다고 생각했을때 홀 수 줄의 짝 수 컬럼과, 짝 수 줄의 홀 수 컬럼은 각각 같은 값을 가져야 한다.

 

나는 컬럼은 인덱스를 0부터 시작하고, 열은 1부터 시작했기 때문에 위와 같은 조건이 나왔다.

 

 

 

 

sudo code의 흐름은 아래와 같이 정리할 수 있겠다

1. String 줄글로 들어오는 input들을 integer 1차원 배열로 저장
2. 8개씩 잘라서 검사해야하는 대상 축소
3. 홀 수 줄의 짝 수 컬럼과, 짝 수 줄의 홀 수 컬럼은 각각 같은 값을 가져야 한다는 조건으로 두 가지 경우(흰검,검흰)에 대한 count진행
4. 각 count중에 작은 값을 결과 list에 삽입
5. 4번 list에서 가장 작은 값이 정답

 

 

 

 

 

실제 구현 방향

실행시간 단축을 위해 BufferedReader, BufferedWriter, StringBuffer를 사용했다.

 

1. Input을 1차원 배열로 저장

int givenRow = Integer.parseInt(st.nextToken()); //row
int givenColumn = Integer.parseInt(st.nextToken()); //column
List<Integer> targets = new ArrayList<>(); //place for input 1 dimensional array

StringToken을 이용해서 input 열과 행 정보를 저장했다.

 

줄글로 들어올 검흰 정보는 targets이라는 ArrayList에 저장하기로 했다.

 

사실 int array로 구현해 놨는데 자꾸 outOfIndex 에러가 떠서 일단 궁여지책으로 list로 수정해서 진행했다.

 

 

 

 

 

for(int i=0;i<givenRow;i++){
    temp = bf.readLine();
    for(int j=0;j<givenColumn;j++){
        targets.add(temp.toUpperCase().charAt(j) == 'B' ? -1 : 1);
    }
}

줄마다 들어오는 정보를 받아서 검은색일 경우에는 -1으로 하얀색일 경우에는 1으로 저장한다.

 

BWBW
WBWB

만약 들어오는 경우가 위와 같다면 배열은 이렇게 정의된다.

[-1, 1, -1, 1, -1, 1, -1, 1]

 

 

 

 

2. 8X8 대상 값들을 다시 골라내기

문제에서 8X8으로 잘라내 검사한다고 명확히 설명하고 있으므로 해당하는 숫자들을 desired row, desired column으로 설정하여 다시 가공해주었다.

 

 int rowPosition = i / givenColumn + 1; //주어진 input에서 원래 열의 자리를 찾는 방법
 int colPosition = i % givenColumn; //주어진 input에서 원래 행의 자리를 찾는 방법

if(colPosition + desiredRow > givenRow || rowPosition + desiredRow - 1 > givenRow) continue; //위의 시작점에서 요구되는 길이만큼 옆과 아래가 존재하는지 체크

일차원 배열로 만들었던 값들 중에서 가로 8개, 세로 8개를 골라내야 하므로 위처럼 2차원이라고 가정하고 각각 값들이 넘치지 않는지 체크한다.

 

for(int k=0;k<desiredRow;k++){ 
    for(int l=0;l<desiredColumn;l++){
        group.add(i + l + (givenRow * k));
     }
   }

시작점에서 각각 8개씩 가지고 와도 좋다고 통과되었으면 검사할 그룹이라는 array에 값을 차례대로 넣어준다.

 

 

 

 

 

BBBB
WWWW
BBBB
WWWW

만약 들어오는 경우가 위와 같다면 배열은 [-1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] 이렇게 정의 될 것이고 2X2로 정의된 Target 그룹을 만들게 된다면 아래와 같이 정리할 수 있다.

 

0, 0에서 시작	[-1, -1, 1, 1]
0, 1에서 시작	[1, 1, 1, 1]

한 9개 정도 후보군이 나올 것 같다. 이 경우에는 

 

 

 

 

 

3. 흰 검, 검 흰으로 경우를 나눠 카운트 하기

int count = 0, count2 = 0;

for(int t = 1; t < group.size() ; t++){
int targetIndex = group.get(t);
int innerRowPosition = t / desiredColumn + 1;

int innerColPosition = t % desiredColumn;

boolean condition = (innerRowPosition % 2 != 0 && innerColPosition % 2 == 0) || (innerRowPosition % 2 == 0 && innerColPosition % 2 != 0);

//0,0과 값이 같은경우, 값이 다른 2개의 경우로 count 할 수 있다.
if(condition) {
    if(targets.get(targetIndex) != targets.get(group.get(0))) count ++;//0번째 기준으로 생각할때         if(targets.get(targetIndex) != targets.get(group.get(0))*-1) count2 ++;
}else{
    if(targets.get(targetIndex) == targets.get(group.get(0))) count ++;//0번째 기준으로 생각할때      if(targets.get(targetIndex) == targets.get(group.get(0))*-1) count2 ++; }
}
    results.add(count < count2+1 ? count : count2+1);
}

여기서 핵심은 condition부분이다.

 

 

열은 인덱스가 0에서 시작하고, 행은 1에서 시작하기 때문에 아래와 같은 조건이 필요하다.

0,0과 같은 값 => 홀수 줄, 짝수 행의 값은 0,0과 같아야 하고 나머지는 달라야 한다.

이 조건을 기준으로 condition을 정의했다.

 

 

 

 

 

4. 정리한 리스트에서 가장 작은 값 불러오기

리스트 가장 작은 Collection을 이용해서 가지고 왔다.

Collections.min(results).toString());

 

 

 

 

 

 

전체 코드(정답 코드 x)

import java.io.*; import java.util.*; public class Main {     static BufferedReader bf;     static BufferedWriter bw;     //static StringTokenizer st     //평균, 중앙, 최빈, 범위     public static void main(String[] args) throws IOException {         bf = new BufferedReader(new InputStreamReader(System.in));         bw = new BufferedWriter(new OutputStreamWriter(System.out));         StringTokenizer st = new StringTokenizer(bf.readLine());         String temp = "";         int desiredColumn = 8, desiredRow = 8;         int givenRow = Integer.parseInt(st.nextToken()); //row         int givenColumn = Integer.parseInt(st.nextToken()); //column         List<Integer> targets = new ArrayList<>();         List<Integer> results = new ArrayList<>();         for(int i=0;i<givenRow;i++){             temp = bf.readLine();             for(int j=0;j<givenColumn;j++){                 targets.add(temp.toUpperCase().charAt(j) == 'B' ? -1 : 1);         }         }         for(int i=0;i<targets.size();i++){             int rowPosition = i / givenColumn + 1;             int colPosition = i % givenColumn;             List<Integer> group = new ArrayList<>();             if(colPosition + desiredRow > givenRow || rowPosition + desiredRow - 1 > givenRow) continue;             for(int k=0;k<desiredRow;k++){                 for(int l=0;l<desiredColumn;l++){                     group.add(i + l + (givenRow * k));                 }             }             int count = 0, count2 = 0;             for(int t = 1; t < group.size() ; t++){                 int targetIndex = group.get(t);                 int innerRowPosition = t / desiredColumn + 1;                 int innerColPosition = t % desiredColumn;                 boolean condition = (innerRowPosition % 2 != 0 && innerColPosition % 2 == 0) || (innerRowPosition % 2 == 0 && innerColPosition % 2 != 0);                 if(condition) {                     if(targets.get(targetIndex) != targets.get(group.get(0))) count ++;//0번째 기준으로 생각할때                     if(targets.get(targetIndex) != targets.get(group.get(0))*-1) count2 ++;                 }else{                     if(targets.get(targetIndex) == targets.get(group.get(0))) count ++;//0번째 기준으로 생각할때                     if(targets.get(targetIndex) == targets.get(group.get(0))*-1) count2 ++;                 }             }             results.add(count < count2+1 ? count : count2+1);         } //        bw.write(results.toString());         bw.write(Collections.min(results).toString());         bw.flush();         bw.close();     } }

 

 

 

 

 

흠.. 어디가 잘못된 걸까. 찬찬히 뜯어보며 고쳐봐야겠다.