[프로그래머스] Level 3. 외벽 점검

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

프로그래머스

 

해결 방법(실패, 시간초과)

1. 가장 많이 걸을 수 있는 친구 순서대로 나열한다.
2. 첫 번째 친구부터, 각 지점 (시계, 반시계) 를 모두 돌아보며 완전 탐색을 진행한다.
3. 만약 남은 외벽이 없거나, 더이상 친구가 없다면 재귀를 종료한다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> friends;
int max_friend;
int wall_length= 0;
int answer = -1;

int get_dist(int s, int e, bool clockwise){
    if(clockwise){
        if(e>=s) return e-s;
        return e+wall_length-s;
    }else
    {
        if(e<=s) return s-e;
        else return wall_length-e+s;
    }
}

vector<int> check(vector<int> remains, int start, int dist, bool clockwise){
    
    vector<int> r ;
    for(int i=0; i<remains.size(); i++){
        if(get_dist(start,remains[i],clockwise) > dist){
            r.push_back(remains[i]);
        } 
    }
    return r;
}
void dfs(vector<int> remains, int fcnt){ //점검완료지점. 사용한 친구 수 
    
//    cout <<"사용된 친구:"<<fcnt <<", 남은 외벽 "<<remains.size()<<endl;
    if(remains.size()== 0){
        if(answer == -1) answer = fcnt;
        else answer = min(answer, fcnt);
        return;
    }
    if(fcnt == max_friend ) return ; //외벽점검을 완료할 수 없음.
    
    int dist = friends[fcnt];
    //남은 외벽들을 왼/오른쪽으로 탐색
    for(int i = 0; i<remains.size(); i++){
        //시계방향 탐색
        vector<int> r = check(remains, remains[i], dist, true);
        
//        cout <<fcnt<<"번째 친구 사용(시계). 남은 외벽:"<<r.size();
        dfs(r, fcnt+1);
        
        r = check(remains,remains[i],dist,false);
//        cout <<fcnt<<"번째 친구 사용(반시계). 남은 외벽:"<<r.size();
        dfs(r,fcnt+1);
    }
}
int solution(int n, vector<int> weak, vector<int> dist) {
    
    //이동거리가 큰 친구부터 정렬
    sort(dist.rbegin(), dist.rend()); 
    wall_length =n;
    friends = dist;
    max_friend = dist.size();
    
    
    dfs(weak, 0);

    return answer;
}

 

이 문제는 해답은 찾을 수 있으나, 시간초과가 발생했다. 조금 더 효율적인 방법을 생각할 필요가 있었다.

 

개선 1 (실패, 시관초과 2개)

 생각해보니, 시계, 반시계 방향을 고려할 필요가 있을까?? 친구 A가 1->5 번까지 시계방향으로 이동한 것과 5->1 번으로 시계방향 이동한 것은 동일하다. 따라서 시계방향과 관련된 정보를 제거하고, dfs 재귀도 한번으로 변경했다. 이전 코드보다는 시간초과가 훨씬 줄어들었지만, 여전히 2개의 문제에서 시간초과가 발생하였다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> friends;
int max_friend;
int wall_length= 0;
int answer = -1;

int get_dist(int s, int e){
    if(e>=s) return e-s;
    return e+wall_length-s;
}

vector<int> check(vector<int> remains, int start, int dist){
    
    vector<int> r ;
    for(int i=0; i<remains.size(); i++){
        if(get_dist(start,remains[i]) > dist){
            r.push_back(remains[i]);
        } 
    }
    return r;
}
void dfs(vector<int> remains, int fcnt){ //점검완료지점. 사용한 친구 수 
    
//    cout <<"사용된 친구:"<<fcnt <<", 남은 외벽 "<<remains.size()<<endl;
    if(remains.size()== 0){
        if(answer == -1) answer = fcnt;
        else answer = min(answer, fcnt);
        return;
    }
    if(fcnt == max_friend ) return ; //외벽점검을 완료할 수 없음.

    //외벽 탐색 후 검사가 필요한 외벽 리스트 r을 반환
    for(int i = 0; i<remains.size(); i++){
        vector<int> r = check(remains, remains[i], friends[fcnt]);
        dfs(r, fcnt+1);
    }
}
int solution(int n, vector<int> weak, vector<int> dist) {
    
    //이동거리가 큰 친구부터 정렬
    sort(dist.rbegin(), dist.rend()); 
    wall_length =n;
    friends = dist;
    max_friend = dist.size();
    
    
    dfs(weak, 0);

    return answer;
}

 

 

아예 다른 방법으로 접근할수밖에.. 아 한개만 시간초과인데 ㅠㅠ

해결방법(성공)

순열을 이용해서 문제를 푼다.  (Brute-Force)

순열(permutation) 이란 , 주어진 요소들의 순서를 바꿔가며 가느한 모든 경우를 만들어 내는 것을 의미한다. 예를들어 dist = {1,2,3} 일 경우 아래처럼 모든 가능한 순서를 만들어서 각각의 경우에 대해 탐색한다.

1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

이 문제에서 어려운 점은 원형 배열 즉, N다음이 0으로 순회한다는 점이다. 이를 단순화하기 위해, weak배열을 2배로 확장한다. 예를들어 n = 12 이고 weak = [1,5,6,10] 이라면 확장된 weak 배열 = [1,5,6,10,13,17,18,22] 이다.  이렇게 하면 시계방향으로만 순차 탐색하여도 원형 배열을 고려한 것과 같게된다.

 

친구들의 순서를 바꿔가면서 순서대로 벽을 점검하게 하고, 가장 최소한의 친구가 필요한 경우를 찾는다.

 

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

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = dist.size() + 1; // 최소한의 친구 수를 찾기 위해 초기값을 큰 값으로 설정
    int length = weak.size();

    // 1. **배열을 2배 길이로 변환**
    for (int i = 0; i < length; i++) {
        weak.push_back(weak[i] + n); // 원형 구조를 직선으로 변환
    }

    // 2. **모든 시작점에 대해 탐색**
    for (int start = 0; start < length; start++) {

        // 3. **순열을 이용해 친구를 배치하는 모든 경우 탐색 (while 사용)**
        sort(dist.begin(), dist.end()); // 순열을 위해 정렬
        bool hasNextPermutation = true; // 순열이 있는지 확인하는 변수
        
        while (hasNextPermutation) {
            int cnt = 1; // 사용한 친구 수
            int position = weak[start] + dist[cnt - 1]; // 첫 번째 친구가 도달할 수 있는 위치

            // 4. **점검할 위치 탐색**
            for (int index = start; index < start + length; index++) {
                if (position < weak[index]) { // 친구가 점검할 수 없는 곳 발견
                    cnt += 1; // 새로운 친구 투입
                    if (cnt > dist.size()) break; // 친구를 모두 써도 점검 불가능하면 종료
                    position = weak[index] + dist[cnt - 1]; // 다음 친구가 도달할 수 있는 위치 업데이트
                }
            }

            // 5. **최소한의 친구 수 갱신**
            answer = min(answer, cnt);

            // 6. **다음 순열 생성**
            hasNextPermutation = next_permutation(dist.begin(), dist.end());
        }
    }

    // 7. **최소 친구 수가 dist.size()보다 크면 모든 지점을 점검할 수 없다는 뜻**
    return answer > dist.size() ? -1 : answer;
}

 

 

내가 처음에 이 코드를 보고 든 의문은 이거였다.

그러면 순열을 이용해서 친구들의 순서를 바꿔가며 모든 경우를 찾는거잖아, 근데 왜 모든 시작점에 대해 탐색하는거야?? 
친구가 3명이라 가정하면 {1,2,3}{1,3,2}.. 총 6개의 방법으로 친구들을 순서를 매기고,
그 순서대로 0번째 벽부터 검사하는 거잖아, 그러면 맨 위에있는 for문은 필요없는거아니야??

 

 

🔹 모든 시작점에 대해 탐색하는 이유

🧐 반례 생각해보기

친구가 3명(dist = {1, 2, 3})이고, 약한 지점(weak)이 {1, 5, 6, 10}이라고 가정해볼게요.

1. 우리가 next_permutation()을 이용해서 {1,2,3}, {1,3,2}, {2,1,3}, ... 식으로 친구들의 순서만 바꾼다면,
   어느 지점부터 시작할지는 고정된 상태가 됩니다.
   → 즉, weak[0] = 1부터만 탐색하면 출발 지점이 최적이 아닐 수도 있음.
2. 하지만 weak이 원형으로 이어진 벽이기 때문에, 어느 약한 지점부터 시작하느냐에 따라 점검할 수 있는 구역이 달라집니다.
   • {1, 5, 6, 10}에서 1부터 시작하는 경우와 5부터 시작하는 경우의 점검 방식이 달라질 수 있음.
3. 친구들의 순서가 같더라도 어느 위치에서 시작하느냐에 따라 최소 인원이 달라질 수 있음.
   예제 분석:
   • {1,2,3} 순서로 weak[0] = 1에서 시작하면 친구 3명이 필요할 수도 있지만,
   • 같은 {1,2,3} 순서로 weak[1] = 5에서 시작하면 친구 2명으로 끝낼 수도 있음.

👉 즉, 친구 순서만 바꾼다고 해서 최소 인원을 찾을 수 있는 게 아님!
👉 벽의 어느 지점에서 점검을 시작하는지도 최적의 해를 찾는 중요한 요소!

 

오케이! 알았따

 

내가 푼 DFS 방법과 순열을 이용한 방법의 시간복잡도는 어떻게 될까??

1. 순열을 이용한 방법

시간 복잡도 분석

1. 친구 순열의 경우의 수
   • dist의 최대 크기 = 8
   • 순열의 개수 = O(8!) = 40,320 (최악의 경우)
2. 모든 시작점을 고려
   • weak의 최대 크기 = 15
   • 모든 weak[i]를 시작점으로 고려 → O(15)
3. 각 순열에 대해 O(N)의 탐색 수행
   • 한 번의 순열당 weak을 검사하는 반복문 수행 → O(N)

총 시간 복잡도

O(8!×15×N)=O(40,320×15×N)O(8! \times 15 \times N) = O(40,320 \times 15 \times N)O(8!×15×N)=O(40,320×15×N)

최악의 경우 600,000N 정도의 시간이 소요된다.

 

 

2. DFS를 이용한 방법

시간 복잡도 분석

1. DFS 탐색 깊이
   • 최대 dist.size()까지 깊이 탐색 (O(K), 최대 K=8)
2. DFS의 분기 개수
   • weak의 개수만큼 분기 (O(15))
3. 각 DFS 호출마다 O(N)의 연산 수행
   • check() 함수에서 remains를 검사하는 연산 수행.

총 시간 복잡도

O(N×15K)O(N \times 15^K)O(N×15K)

K=8일 때 → O(N \times 15^8) ≈ O(15^8) = O(2.5억)

 

차이가,.많이나네..ㅎㅎ..

 

 

✅ 순열 vs DFS: 언제 사용해야 할까?

 

1️⃣ 순열(Brute-force)이 적절한 경우

"몇 개의 요소를 특정 순서로 배치하는 경우의 수를 모두 확인해야 할 때"
"순서가 중요한 경우"

✅ 판단 기준

• 요소(예: 친구, 병력 등)의 순서가 바뀌면 결과가 달라지는 경우.
• 주어진 요소를 하나씩 선택하여 배치하면서 해결해야 하는 경우.
• **요소 개수(K)**가 작을 때 (K!이 감당 가능한 수준인지 확인).
• 조합이 아닌 순열이 필요한 문제(즉, 같은 요소라도 순서가 다르면 다른 경우).

✅ 예제 문제

1. 외벽 점검 문제
   • dist(친구들)을 어떻게 배치하느냐가 결과에 영향을 미침 → 순열
   • 즉, {1,2,3}과 {3,2,1}은 서로 다른 경우이므로 순열을 고려해야 함.
2. N개의 공을 특정 위치에 배치하는 문제
   • 예: 3개의 공을 5개의 칸에 배치하는 모든 방법을 고려해야 한다면 → 순열
3. 가장 긴 문자열을 만들 수 있는 순서 찾기
   • 예: {"apple", "banana", "cherry"}를 조합하여 가장 긴 문자열을 만들 때 → 순열 탐색

📌 시간 복잡도 주의

• 요소 개수(K)가 8 이하면 K! 연산을 감당 가능 → 순열 사용
• K=10이면 10! = 3,628,800 → 가능할 수도 있음
• K=12 이상이면 순열 사용 불가능 (12! = 479,001,600) 🚨

---

2️⃣ DFS(백트래킹)이 적절한 경우

"완전 탐색이 필요하지만, 가지치기를 통해 탐색량을 줄일 수 있을 때"
"순서가 중요하지 않거나, 특정 조건을 만족하는 경로를 찾을 때"

✅ 판단 기준

• 요소의 순서가 중요하지 않을 때 (즉, {1,2,3}과 {3,2,1}이 같은 경우로 취급될 때).
• 완전 탐색을 하되 불필요한 탐색을 줄이는 가지치기가 가능할 때.
• 트리 형태로 탐색이 가능할 때 (예: 그래프 탐색, 조합 탐색).
• 가능한 경우의 수가 너무 많아서 모든 경우를 볼 수 없을 때 → 백트래킹(가지치기) 사용.

✅ 예제 문제

1. 미로 탐색 문제 (최단 경로 찾기)
   • 미로의 모든 경로를 탐색하지만 이미 최적해를 찾으면 더 이상 탐색하지 않음 → DFS+백트래킹
2. N-Queens 문제 (체스판에 퀸 배치하기)
   • 퀸을 배치하는 모든 경우를 탐색하지만, 불가능한 경우는 가지치기(백트래킹)로 제거
3. 경로 찾기 문제
   • 특정 조건을 만족하는 경로를 찾는 문제
   • 예: 그래프 탐색 (DFS/BFS)

📌 시간 복잡도 주의

• DFS의 탐색 깊이(D)가 10 이하면 → DFS 사용 가능 (O(N^D))
• D=15 이상이면 DFS로 탐색할 경우 너무 많은 연산 필요 🚨
• 백트래킹을 잘 활용하면 O(N^D)에서 실제 탐색 횟수를 훨씬 줄일 수 있음.