[C] BOJ 1018- Brute force는 꼼꼼함이 중요한 것 같다

내가 이걸 2021년 7월 21일에 푼 흔적이 있다... 보자마자 머리가 하얘졌는데 과거의 나는 과연 어떻게 푼 걸까? 과외쌤이랑 같이 풀었겠지?

POSCAT 2주차 알고리즘 초급 세미나 때 풀었던 문제이다.
Hint: 홀짝성 이라는 것만 듣고 수업이 끝났다

고1 때 별 찍기 문제를 풀면서 배열의 대각선은 i+j index의 합이 일정하다는 성질은 많이 쓴 적 있었다. 따라서 체스판은 i+j의 홀짝성에 따라 검, 흰이 결정되는 성질을 가지고 있기 때문에 이를 바탕으로 풀어 보았다.

처음에는
arr[i][j](시작 지점)이 W인 경우, B인 경우로 나눠서 풀었고
diag_sum이라는 변수를 만들어서 arr[i+k][j+diag_sum-k]로 탐색을 했지만 배열의 빈 부분(?)까지 탐색하면서 오류가 발생하는 문제가 있었다.

이런 느낌?

W로 시작할 때의 답 ansW, B로 시작할 때의 답 ansB를 따로 계산한 다음에 둘 중 작은 것을 선택하는 게 코드가 더 깔끔하게 나온다.

이게 뭐라고 1시간 반을 썼냐... 하다 보면 늘겠지.

Solution

#include <stdio.h>

int main()
{
  int n, m;
  int i, j; //starting index
  char arr[50][50]={};
  scanf("%d %d", &n, &m);
  for(i=0; i<n; i++)
    scanf("%s", &arr[i]);
  int k=0, l=0; //searching through 8x8 index
  int ansW=64, ansB=64;
  int ansW_temp=0, ansB_temp=0;
  for(i=0; i<n-7; i++)
  {
    for(j=0; j<m-7; j++)
    {
      ansW_temp=0, ansB_temp=0;
      for(k=0; k<8; k++)
      {
        for(l=0; l<8; l++)
        {
          if((k+l)%2 ==0)
          {
            if(arr[i+k][j+l]=='W')
              ansW_temp++;
            else
              ansB_temp++;
          }
          else
          {
            if(arr[i+k][j+l]=='B')
              ansW_temp++;
            else
              ansB_temp++;
          } 
        }
      }  
      if(ansW>ansW_temp) ansW = ansW_temp;
      if(ansB>ansB_temp) ansB = ansB_temp;
    }
  }
  
  if(ansW<ansB)
    printf("%d", ansW);
  else
    printf("%d", ansB);
}

시간복잡도

4중 for문이지만 안쪽 2개는 8x8 체스판으로 숫자가 한정되어 있으므로 시간복잡도는 O(mn)이다.
n, m<50이고 시간제한이 2초인 것을 고려하면 충분한 것으로 보인다.

💡 오늘의 기초 지식: 컴퓨터는 1초에 연산을 1억 (10^8)번 할 수 있다.
시간초과 안 먹기 위한 기본 지식이니 알아두자.