[완전 탐색, DP] (프로그래머스 Lv 3) 외벽 점검

문제

• 문제 링크
• 문제 설명: 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있어 친구들을 보내 점검하고자 한다. 빠른 공사를 위해 점검 시간을 1시간으로 제한했다. 외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 반환하는 함수를 작성
  • 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리
  • 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동

• 입력
  • n은 1 이상 200 이하인 자연수
  • weak의 길이는 1 이상 15 이하
  • 취약 지점의 위치는 오름차순으로 정렬
  • weak의 원소는 0 이상 n - 1 이하인 정수
  • dist의 길이는 1 이상 8 이하
  • dist의 원소는 1 이상 100 이하인 자연수
• 출력: 친구 수의 최솟값
  • 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 반환

n	weak	dist	result
12	[1, 5, 6, 10]	[1, 2, 3, 4]	2
12	[1, 3, 4, 9, 10]	[3, 5, 7]	1

풀이

• dist 배열을 내림차순으로 정렬
• 각 친구마다 weak의 각 위치에 배치해보면서 시계방향, 반시계방향으로 점검하는 경우를 모두 시도해서 모든 취약 지점이 점검되는 경우 최소 친구 수를 탐색
• dist 배열의 크기가 최대 8이고, weak 배열의 크기가 최대 15이기 때문에 매 취약 지점마다 각 친구를 배치하는 경우를 모두 탐색할 수 있다고 생각해서 완전 탐색으로 풀었는데 시간 초과 발생
  • 현재 배치될 친구 인덱스와 점검한 weak 목록에 대해 부분 문제가 발생하므로 DP로 최적화
• 정답 코드

#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int N;
const int INF = 1e9;
int dp[8][1<<15];

int dfs(int pos, vector<int>& dist, vector<int>& weak, int checked) {
    // 모든 취약지점이 점검되었다면 0을 반환
    if (__builtin_popcount(checked) == weak.size()) return 0;
    if (pos == dist.size()) return INF; // 모든 친구가 배치되었으면 INF
    int& ret = dp[pos][checked];
    if (ret != -1) return ret;
    ret = INF;
    for (int i = 0; i < weak.size(); i++) {
        if (checked & (1 << i)) continue;
        // 시계 방향
        int newChecked = checked;
        int maxPos = weak[i] + dist[pos];
        for (int j = i; ; j++) {
            if (j == weak.size()) { // 끝에 도달한 경우 첫번째 취약 지점으로 인덱스 갱신
                j = 0;
                // 최대 이동 가능 지점도 갱신. 정북 지점을 지나지 않으면 -1
                maxPos = weak[i] + dist[pos] > N ? maxPos % N : -1;
            }
            // 아직 점검되지 않았고 이동 반경 내에 있으면 점검
            if (!(newChecked & (1 << j)) and weak[j] <= maxPos)
                newChecked |= (1 << j);
            else break;
        }
        ret = min(ret, dfs(pos+1, dist, weak, newChecked) + 1);
        // 반시계 방향
        newChecked = checked;
        int minPos = weak[i] - dist[pos];
        for (int j = i; ; j--) {
            if (j < 0) { // 첫번째 지점에 도달한 경우 마지막 취약 지점으로 인덱스 갱신
                j = weak.size()-1;
                // 최대 이동 가능 지점도 갱신. 정북 지점을 지나지 않으면 N
                minPos = weak[i] < dist[pos] ? minPos + N : N;
            }
            if (!(newChecked & (1 << j)) and weak[j] >= minPos)
                newChecked |= (1 << j);
            else break;
        }
        ret = min(ret, dfs(pos+1, dist, weak, newChecked) + 1);
    }
    return ret;
}

int solution(int n, vector<int> weak, vector<int> dist) {
    N = n;
    sort(dist.begin(), dist.end(), [&](int a, int b) mutable { return a > b; });
    memset(dp, -1, sizeof(dp));
    int ret = dfs(0, dist, weak, 0);
    return ret == INF ? -1 : ret;
}