[DFS] 프로그래머스 외벽 점검 C++, Python

 

https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

#include <vector>

using namespace std;

int N, W, D, answer;
vector<int> Weak, Dist;
int order[9], visited[9];

void check(int depth, int start, int place) {
    if (place == W) {
        answer = min(answer, depth);
        return;
    }
    if (depth == D) return; // 친구
    
    int now = start;
    int end = (Weak[start] + Dist[order[depth]]);
    
    while (true) {
        if (Weak[now] > end) break;
        now++;
        place++; // 확인 지점 개수
        if (now >= W) {
            now %= W;
            end = (Dist[order[depth]] - (N - Weak[start])); // % X, 남은 길이 N 이용
        }
        if (place == W) break;
    }
    
    check(depth+1, now, place);
}

void dfs(int depth) { // 순열
    if (depth == D) {
        for (int i=0; i<W; i++) check(0, i, 0); // 양방향
        return;
    }
    
    for(int i=0; i<D; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        order[depth] = i;
        dfs(depth+1);
        visited[i] = false;
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    N = n;
    W = weak.size();
    D = dist.size();
    answer = 1e9;
    
    Weak = weak;
    Dist = dist;
    
    dfs(0);
    
    return (answer == 1e9)? -1 : answer;
}

from itertools import permutations

def solution(n, weak, dist):
    answer = len(dist) + 1
    weak_points = weak + [w + n for w in weak]
    for i, start in enumerate(weak):
        for friends in permutations(dist, len(dist)):
            cnt = 1
            pos = start
            for friend in friends:
                pos += friend
                if pos < weak_points[i + len(weak) - 1]:
                    cnt += 1
                    pos = [w for w in weak_points[i+1:i+len(weak)] if w > pos][0]
                else:
                    answer = min(answer, cnt)
                    break
    if answer > len(dist):
        return -1
    return answer