[백준 15684] 사다리 조작

www.acmicpc.net/problem/15684

15684번: 사다리 조작

계속 시간초과와 원인모를 틀렸습니다를 받은 문제..

dfs를 사용해서 구현하는 문제이다. 

 

전체 배열에서 a번째 줄 b와 b+1 사다리가 연결되어 있다면 arr[a][b] =true로 표시한다.

이렇게 표시한 사다리는 i번째 사다리가 i번째에 도달하는지 확인할 때 왼쪽 오른쪽 모두 확인해서 현재 위치를 col +-1해줘야 한다.

 

추가된 사다리가 4이상이면 -1을 출력하라고 했으므로 cnt>3이면 return;하여 함수를 종료시킨다.

result값이 정해지면 (하나라도 사다리 값이 나오면) 그 이상 함수를 진행하지 않기 위해 if(result != 4) return; 조건을 추가해야 한다. 아니면 TLE가 발생함 ㅠ

result는 최솟값을 리턴해야 하므로 매번 비교해줘야 한다. 아니면 틀린다!!

 

#include <stdio.h>

using namespace std;
int n, m, h, ladders;
bool arr[31][11];
int result = 4;

bool isValid()
{
  for (int i = 1; i <= n; i++)
  {
    int curC = i;
    for (int j = 1; j <= h; j++)
    {
      if (arr[j][curC])
      {
        curC++;
      }
      else if (arr[j][curC - 1])
      {
        curC--;
      }
    }

    if (curC != i)
    {
      return false;
    }
  }
  return true;
}

void BackTracking(int row, int cnt)
{
  if (result != 4)
  {
    return;
  }

  if (cnt > 3)
  {
    return;
  }

  if (cnt == ladders)
  {
    if (isValid())
    {
      result = result > cnt ? cnt : result;
    }
    return;
  }

  for (int i = row; i <= h; i++)
  {
    for (int j = 1; j < n; j++)
    {
      if (arr[i][j] || arr[i][j - 1] || arr[i][j + 1])
        continue;

      arr[i][j] = true;
      BackTracking(i, cnt + 1);
      arr[i][j] = false;
    }
  }
}

int main(void)
{
  scanf("%d%d%d", &n, &m, &h);

  for (int i = 0; i < m; i++)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    arr[a][b] = true;
  }

  for (int i = 0; i <= 3; i++)
  {
    ladders = i;
    BackTracking(1, 0);
    if (result != 4)
    {
      printf("%d\n", result);
      return 0;
    }
  }
  printf("-1\n");

  return 0;
}