백준 NM과 K(1)

진짜 오래 걸린 문제였다. 단순 백트래킹으로 구현하여 답도 제대로 나오는데, 95프로에서 계속 틀렸다고 나와서 정신이 나가는 줄 알았다.

 

#include <iostream>

using namespace std;

int n,m,k;
int isused[12][12];
int arr[12][12];
int lst[12];
int ans = -2147483648;

void func(int row, int col, int lim)
{
  if (lim == k)
  {
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (isused[i][j] == 1)
          sum += arr[i][j];
      }
    }

    ans = max(ans, sum);
    return ;
  }
  for (int i =row; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (isused[i][j] == 0  )
      {
        if (i >= 1 && isused[i-1][j]) continue;
        if (i < n -1 && isused[i+1][j]) continue;
        if (j >= 1 && isused[i][j-1]) continue;
        if (j < m -1 && isused[i][j+1]) continue;
        isused[i][j] = 1;
        func(i,j, lim+1);
        isused[i][j] = 0;
      }
    }
  }
}

int main()
{
  cin>>n>>m>>k;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin>>arr[i][j];
    }
  }

  func(0,0, 0);

  cout<<ans<<"\n";
  return 0;
}

평상시 풀던 백트래킹 구현과 차이가 거의 없다. 사실 나의 실수이자 버릇같은 건데, 이런 이차원 배열 문제를 풀 때 인덱스를 의도적으로 0부터 시작하지 않고 1부터 시작한다. 이렇게 하면 주변을 탐색할 때 0 이하 범위를 참조해 세그폴트가 나지 않는다는 장점이 있는데, 예전부터 이 부분에서 범위 등 에서 계속 틀리는 원인이 됐었다. 그래서 0부터 시작했다

또, max 값 초기화를 0으로 했다가 음수로 바꾸어 주었다.. 이 부분이 가장 큰 실수 였다..!!