[C++] 프로그래머스 - 외벽 점검

2020 KAKAO BLIND RECRUITMENT (2020 카카오 블라인드 채용 문제)

 

취약지점을 몇명의 친구들로 확인 할 수 있는지 찾는 문제입니다.

취약지점이 위의 이미지 처럼 원형모양에 각각 분배되어있습니다.
각 친구들은 확인할 수 있는 거리가 다릅니다.

1. 가장 많이 볼 수 있는 친구를 취약점 위치에 배치
2. 취약점 위치로부터 시계방향으로 취약점들 제거
3. 제거된 취약점과 해당 친구를 제외하고 1~2 반복
4-1. 모든 취약점 제거시 true와 현재 깊이값을 반환
4-2. 취약점 제거하지 못한 상태에서 더 이상 친구가 없는 경우 false 반환
5. true인 경우 깊이값이 가장 작은 값을 반환, false인 경우 -1을 반환

DFS를 활용해서 문제를 해결했습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

tuple<int, bool> func(int n, vector<int> weak, vector<int> dist)
{
  int count = 200;

  for (int i = 0; i < weak.size(); ++i)
  {
    if (dist.size() == 0)
    {
      return make_tuple(0, false);
    }

    vector<int> tempWeak = weak;
    vector<int> tempDist = dist;

    int num = tempWeak[i];
    int dis = dist.back();
    int index = i;

    while (dis >= 0 && tempWeak.size() > 0)
    {
      tempWeak.erase(tempWeak.begin() + index); 
      if (tempWeak.size() == 0)                 
      {
        return make_tuple(1, true);
      }
      if (i >= tempWeak.size()) 
      {
        index = 0;
      }

      dis -= min(abs(tempWeak[index] - num), abs(n - num + tempWeak[index]));
      num = tempWeak[index];                                                  
    }
    tempDist.erase(tempDist.end() - 1); 

    if (tempDist.size() > 0 && tempWeak.size() > 0) 
    {
      tuple<int, bool> returnData; 
      returnData = func(n, tempWeak, tempDist);
      if (get<1>(returnData))
      {
        count = min(count, get<0>(returnData));
      }
    }
  }

  if (count == 200)
  {
    return make_tuple(1, false);
  }

  return make_tuple(count + 1, true);
}

int solution(int n, vector<int> weak, vector<int> dist)
{
  int answer;

  tuple<int, bool> returnData;
  returnData = func(n, weak, dist);
  if (!get<1>(returnData))
  {
    return -1;
  }
  answer = get<0>(returnData);

  return answer;
}