[C++로 풀이] 외벽 점검 (완전 탐색, DFS, 비트 연산으로 방문 체크)⭐⭐⭐

📌 외벽 점검

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

🔥 1 차 풀이 (시간초과⏰)

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

using namespace std;

bool found = false;
int north; // n
void DFS(int& num, vector<int>& weak, vector<bool>& weak_visited, vector<int>& friends, int depth) {
    // num 은 설정한 필요한 친구 수
    if (depth == num) {
        // 진짜 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었다면 found 를 true 로 만들기
        bool completed = true;
        for (int i = 0; i < weak_visited.size(); ++i) {
            if (weak_visited[i] == false) {
                completed = false;
                break;
            }
        }
        if (completed)
            found = true;
        return;
    }

    // start : 점검하기 시작할 외벽 시작점
    for (int start = 0; start < weak.size(); ++start) {
        // 이미 점검한 외벽이면 넘어감
        if (weak_visited[start])
            continue;

        // 외벽 체크하기 전의 점검 상태 미리 옮겨놓고 보존 (초기 상태)
        // DFS 돌아와서 복원할 수 있도록
        vector<bool> before = weak_visited;

        // 반시계 방향(왼쪽)
        int count = 1; // start 에서 반시계방향으로 돌면서 제거 
        int dest = weak[start] - friends[depth]; // 반시계 방향으로 해당 start 위치 외벽으로부터 현재 친구가 갈 수 있는 거리로 갈 수 있는 '위치'
        int i = start; // start 외벽에서부터 반시계 방향으로 점검할 것
        bool flag = false; // 왼쪽으로 가다가 범위 넘어가버릴 때 (순환해야 해서)
        while (count <= weak.size()) {   // 점검 완료한 개수 count 가 전체 외벽 개수를 넘을 수는 없음
            if (i < 0) { // 왼쪽으로 가다가 범위를 넘어버리면
                flag = true;
                i += weak.size(); // 오른쪽 끝으로 순환하여 갈 수 있도록 i 설정
            }
            if (flag) {  // i = 0 이상으로 넘어간 상태라면 (north 빼서 그냥 음수로 보정)
                if (weak[i] - north >= dest) // depth 번째 친구가 커버할 수 있는 곳이라면(= 왼쪽으로 start~dest 범위 내에 있는 외벽들은 점검할 수 있다. 아직 dest 에 도달하지 않았다면 점검할 수 있는 외벽). 예를들어 1시에서 10시 인 곳으로 범위를 넘어갔다면 10 - 12 = -2 이렇게 -2 시로 취급한다.
                    weak_visited[i] = true; // 점검 체크
                else break;
            }
            else {  //  i = 0 이상으로 넘어간 상태가 아니라면
                if (weak[i] >= dest) // depth 번째 친구가 커버할 수 있는 곳이라면(= 왼쪽으로 start~dest 범위 내에 있는 외벽들은 점검할 수 있다. 아직 dest 에 도달하지 않았다면 점검할 수 있는 외벽)
                    weak_visited[i] = true; // 점검 체크
                else break;
            }

            ++count;; 
            --i; // 반시계방향 (왼쪽)
        }
        DFS(num, weak, weak_visited, friends, depth + 1); // 반시계방향으로 점검 체크한 외벽들 정보를 가지고 이제 depth + 1 번째 친구가 점검하러 재귀 호출
        weak_visited = before; // 복원
        // 위 재귀 호출로 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었음이 밝혀졌다면 더 검사하지 않고 종료
        if (found) 
            return;
        

        // 시계 방향
        count = 1; // start 에서 시계방향으로 돌면서 제거 
        dest = weak[start] + friends[depth]; // 시계 방향으로 해당 start 위치 외벽에서 현재 친구가 갈 수 있는 거리로 갈 수 있는 위치
        i = start; // start 외벽에서부터 시계 방향으로 점검할 것
        flag = false; // 오른쪽으로 가다가 범위 넘어가버릴 때 (순환해야 해서)
        while (count <= weak.size()) {
            if (i >= weak.size()) {
                flag = true;
                i = 0;
            }
            if (flag) {
                if (weak[i] + north <= dest)
                    weak_visited[i] = true;
                else break;
            }
            else {
                if (weak[i] <= dest)
                    weak_visited[i] = true;
                else break;
            }

            ++count;;
            ++i;
        }
        DFS(num, weak, weak_visited, friends, depth + 1);
        weak_visited = before;
        // 위 재귀 호출로 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었음이 밝혀졌다면 더 검사하지 않고 종료
        if (found)
            return;
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
    north = n;
    vector<bool> weak_visited(weak.size()); 
    sort(dist.begin(), dist.end(), greater<int>()); // 가장 많이 점검할 수 있는 친구들이 가장 앞에 오도록 내림차순 정렬
    for (int i = 1; i <= dist.size(); ++i) { // 최소값이 될 수 있는 후보들 (= 필요한 친구 수)
        vector<int> friends;
        friends.assign(dist.begin(), dist.begin() + i); // 검사할 수 있는 친구 수 할당. 크기는 i 만큼.
        DFS(i, weak, weak_visited, friends, 0);
        // 위 재귀 호출로 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었음이 밝혀졌다면 더 검사하지 않고 종료
        if (found) {
            answer = i;
            break;
        }
    }

    return answer;
}

• dist 내림 차순 정렬
  • 친구들을 최소로 투입해야하기 때문에 그러려면 최대한 많이 이동할 수 있는 친구부터 투입해야 한다.
  • 따라서 내림 차순 정렬!
• 이 풀이에서 나는 전체 친구들(dist.size())에서 1 명 (=재귀 깊이 1), 2 명 (=재귀 깊이 2), 3 명 (=재귀 깊이 3),.. 이렇게 차례로 이 친구들 수로 전체 외벽을 점검할 수 있는지를 보았다. 1명부터 차례로 검사했으니 처음으로 외벽 전체를 점검할 수 있는 친구들 수를 찾는다면 그게 답이다.
  • friends에 i명(num)의 친구가 들어가도록 했고 이를 dist 대신 파라미터로 넘겼다.
    • ex) dist가 [2,3,1,4] 라면 내림 차순 정렬하여 [4,3,2,1] 이 되고 차례로 [4], [4,3], [4,3,2], [4,3,2,1] 이런 친구목록일 때 각각 외벽을 모두 점검할 수 있는지 검사하게 된다.

      for (int i = 1; i <= dist.size(); ++i) { // 최소값이 될 수 있는 후보들 (= 필요한 친구 수)
        vector<int> friends;
        friends.assign(dist.begin(), dist.begin() + i); // 검사할 수 있는 친구 수 할당. 크기는 i 만큼.
        DFS(i, weak, weak_visited, friends, 0);
        // 위 재귀 호출로 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었음이 밝혀졌다면 더 검사하지 않고 종료
        if (found) {
            answer = i;
            break;
        }
      }
      

  • 재귀 깊이가 해당 친구 수(num)에 도달했을 때 외벽을 모두 점검하는지를 검사한다.

    if (depth == num) {
        // 진짜 num 명의 친구 수로 으로 모든 외벽을 커버할 수 있었다면 found 를 true 로 만들기
        bool completed = true;
        for (int i = 0; i < weak_visited.size(); ++i) {
            if (weak_visited[i] == false) {
                completed = false;
                break;
            }
        }
        if (completed)
            found = true;
        return;
    }
    

• 순환
  • 반시계방향으로(배열을 왼쪽으로 순회) 돌다보면 i=0을 넘길 수도 있는데 이때 n 을 빼서 보정해준다.
    • 예를 들어 외벽 위치들이 [1,5,6,10] 이고 n 이 12 라면, 반시계 방향으로 돌다가 맨 앞 원소인 1 을 넘어버렸을 때 오른쪽 끝 원소인 10 으로 순환하도록 해야 하는데, 10 - 12 = -2 즉, 10이 아닌 -2로 취급을 한다. dest = weak[start] - friends[depth]; 와 비교를 해야하기 때문이다.
  • 시계방향으로 돌때도 마찬가지. 이땐 범위를 넘으면 n 을 더함.

⏰이 풀이에서 시간 초과가 발생한 이유

반시계 방향은 검사하지 않아도 된다. 반시계, 시계 두 방향 중 하나만 선택해서 검사하면 된다. 중복되기 때문이다! 예를 들어 1 에서 시계방향으로 4 를 가는 것은, 4 에서 반시계 방향으로 1 로 가는 것과 같다. 즉, 똑같은 점검이 두 번 일어나는 것이다. 따라서 두 방향 다 검사하지 않고 한 방향만 검사하면 됐었다.😥

🔥 2 차 풀이 (시간초과⏰)

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

using namespace std;

bool found = false;
int north;
void DFS(int& num, vector<int>& weak, vector<bool>& weak_visited, vector<int>& friends, int depth) {
    
    if (depth == num) {
        bool completed = true;
        for (int i = 0; i < weak_visited.size(); ++i) {
            if (weak_visited[i] == false) {
                completed = false;
                break;
            }
        }
        if (completed)
            found = true;
        return;
    }
    
    for (int start = 0; start < weak.size(); ++start) {

        if (weak_visited[start])
            continue;

        vector<bool> before = weak_visited;

        // 시계 방향
        int count = 1;
        int dest = weak[start] + friends[depth];
        int i = start;
        bool flag = false;
        while (count <= weak.size()) {
            if (i >= weak.size()) {
                flag = true;
                i = 0;
            }
            if (flag) {
                if (weak[i] + north <= dest)
                    weak_visited[i] = true;
                else break;
            }
            else {
                if (weak[i] <= dest)
                    weak_visited[i] = true;
                else break;
            }

            ++count;;
            ++i;
        }
        DFS(num, weak, weak_visited, friends, depth + 1);
        weak_visited = before;
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
    north = n;
    vector<bool> weak_visited(weak.size());
    sort(dist.begin(), dist.end(), greater<int>());
    
    for (int i = 1; i <= dist.size(); ++i) {
        vector<int> friends;
        friends.assign(dist.begin(), dist.begin() + i);
        DFS(i, weak, weak_visited, friends, 0);
        if (found) {
            answer = i;
            break;
        }
    }

    return answer;
}

⏰그래도 여전히 시간초과가 발생하는 이유

반시계방향 검사 부분 코드를 지웠더니 윗 풀이의 결과보다는 시간이 줄었지만 그러나 13번 케이스는 아직도 시간초과 문제가 발생하였다.

내 풀이의 단계는 아래와 같다.

1 ~ dist.size() 순회 (친구 수 정하기) 👉 weak 순회 (시작 외벽 결정)👉 weak 순회 (점검할 수 있는 외벽들 검사)

• 1 ~ dist.size() 순회 (친구 수 정하기)

  int solution(int n, vector<int> weak, vector<int> dist) {
    // ...
    for (int i = 1; i <= dist.size(); ++i) {
        vector<int> friends;
        friends.assign(dist.begin(), dist.begin() + i);
        DFS(i, weak, weak_visited, friends, 0);
  

• weak 순회 (시작 외벽 결정)

  void DFS(int& num, vector<int>& weak, vector<bool>& weak_visited, vector<int>& friends, int depth) {
      // ...
      for (int start = 0; start < weak.size(); ++start) {
  

• weak 순회 (점검할 수 있는 외벽들 검사)

  void DFS(int& num, vector<int>& weak, vector<bool>& weak_visited, vector<int>& friends, int depth) {
       for (int start = 0; start < weak.size(); ++start) {
            while (count <= weak.size()) {
                DFS(num, weak, weak_visited, friends, depth + 1);
  

시간 복잡도를 생각해서 이 과정을 더 줄여야 한다는 이야기다! ㅠㅜ 이 풀이는 외벽 점검을 모두 다하는 순간을 찾자마자 종료되겠지만 입력 크기도 최대인데 외벽 점검을 다 하지 못했을 때의 시간복잡도를 생각해야 한다. 이 과정을 더 줄이고도 답을 찾을 수 있는지를 생각해야 한다.

🔥 3 차 풀이 ⭕

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

using namespace std;

#define INF 9999
int answer;
int north;

void DFS(vector<int>& weak, vector<int>& dist, int depth, int start_weak_pos, int weak_visited){
    // 종료 조건 1 : 모든 친구를 다 투입해도 해당 외벽 시작점 + 순회 경로는 모두 점검할 수 없었던 경우
    if (depth == dist.size())
        return;
    
    // 종료 조건 2 : 이 경로는 현재까지 구한 최소 친구수보다 더 많은 친구수가 필요해서 이 경로로 더 이상 갈 필요가 없는 경우 (가도 answer 보다 더 적은 친구수를 찾아낼 일이 없다.)
    // depth + 1 은 친구수 (depth 는 재귀 단계)
    if (depth + 1 >= answer)
        return;

    // start_weak_pos 시작 외벽부터 시계방향으로 "아직 방문하지 않은" 외벽들을 dist[depth] 친구가 점검한다. 
    for (int i = 0; i < weak.size(); ++i) {
        // 시계 방향
        int next_weak_pos = (start_weak_pos + i) % weak.size(); // start_weak_pos + i 근데 인덱스가 weak 범위를 넘어가 버릴 수도 있으니 나머지
        int distance = weak[next_weak_pos] - weak[start_weak_pos]; // 시작 외벽 start_weak_pos 부터 현재 순회중인 외벽까지의 거리

        // 시계방향(오른쪽)으로 순회하다가 next_weak_pos 가 weak 범위를 넘어가버리면 인덱스 0, 즉 왼쪽부터 다시 시작하게 된다. 이 경우이다! n 을 더해 보정한다.
        if (next_weak_pos < start_weak_pos)
            distance += north; //  weak 는 오름차순 정렬 상태이므로 여기에 걸렸다는건 distance 가 음수가 되었다는 것이다. n 을 더해 보정해준다. -3 이 되었다면 12를 더해 9로 만듬. 즉 거리가 9.

        // dist[depth] 친구가 점검할 수 있는 거리면 "방문 체크를 한다."
        if (distance <= dist[depth]) 
            weak_visited |= (1 << next_weak_pos);
        else break;
    }

    // 종료 조건 3 : 모든 외벽 지점들을 모두 점검한 경우! (즉 모든 외벽이 "모두 방문된 경우") 이 경로는 끝난 것이니 answer를 업뎃하고 돌아간다. 
    if (weak_visited == (1 << weak.size()) - 1) {
        answer = min(answer, depth + 1);
        return;
    }

    // 위의 if 에서 걸리지 못했다면 아직 방문하지 않은 외벽이 남아있다는 얘기다.
    // 아직 방문하지 않은 외벽들을 순회하며 각각 시작점으로 삼고 depth + 1 친구 한명을 더 늘려서 다음 친구가 "방문 하지 않은 나머지 외벽들"을 점검할 수 있을지 검사하러 재귀 호출 ㄱㄱ
    for (int start = 0; start < weak.size(); ++start) {
        if (weak_visited & (1 << start)) 
            continue;
        DFS(weak, dist, depth + 1, start, weak_visited);
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    answer = INF;
    north = n;
    sort(dist.begin(), dist.end(), greater<>()); // 내림차순 정렬

    // 순차적으로 외벽 점검 시작점 정해놓고 재귀호출 
    for (int start = 0; start < weak.size(); ++start) 
        DFS(weak, dist, 0, start, 0);
    
    // answer 가 그대로 INF 라면 외벽을 모두 점검할 수 있는 경우가 전혀 없다는 뜻
    if (answer == INF) return -1;
    return answer;
}

풀이 코드는 아래 유튜브를 참고했다.

이 풀이의 단계는 아래와 같다.

weak 순회 (시작 외벽 결정)👉 weak 순회 (점검할 수 있는 외벽들 검사)

• weak 순회 (시작 외벽 결정)

  int solution(int n, vector<int> weak, vector<int> dist) {
    //..
    for (int start = 0; start < weak.size(); ++start) 
        DFS(weak, dist, 0, start, 0);
  

• weak 순회 (점검할 수 있는 외벽들 검사)

  void DFS(vector<int>& weak, vector<int>& dist, int depth, int start_weak_pos, int weak_visited) {
      //...
      for (int i = 0; i < weak.size(); ++i) {
          DFS(weak, dist, depth + 1, i, weak_visited);
  

내 원래 풀이와 다르게 1 ~ dist.size() 순회 (친구 수 정하기) 이 빠졌다. 대신 모든 weak 의 시작점을 정해놓고 weak 외벽을 모두 점검할 수 있는지를 따지고 모두 점검하지 못할 때 친구 수를 늘리므로써 재귀 호출을 한다.

나는 정답 후보가 될 수 있는 친구 수로 재귀 깊이를 미리 정해두고 결정한 그 친구 수 안에서 외벽 순회 O(N^2) 를 하였고 처음으로 외벽 점검을 모두 할 수 있었던 그 친구 수를 답으로 도출하고 더 이상 진행하지 않았는데, 이 풀이는 친구 수를 미리 정해두는 방식은 취하지 않고 외벽 순회 O(N^2) 를 하면서 해당 친구로 외벽을 다 순회하지 못할 때만 재귀호출로 더 깊게 들어가서 친구 수를 늘려서 순회하는 방식이다. 즉, 완전 탐색으로, 외벽이 선택될 수 있는 모든 경우의 수를 다 구하여 매번 필요한 친구 수들 중 가장 최소값을 저장하는 식이다. 미리 친구 수를 정해두지 않고 외벽 순회의 결과에 맞춰 친구 수가 결정된다.

• 이 풀이는 시간 초과가 나지 않는 이유
  • 1️⃣ 내 풀이는 3단계긴 하지만 순차탐색처럼 친구를 빨리 찾으면 빨리 끝낼 수 있다. 이처럼 친구 수를 빨리 찾는다면 내 원래 풀이가 더 빠르겠지만.. 입력 크기가 최대인 상태인데 지금 친구들로 모든 외벽을 다 점검하지 못했다면? 내 풀이는 3단계고 이 풀이는 2단계이기 때문에 여기서부터 차이가 크게 날 것이다.
  • 2️⃣ 재귀의 깊이 depth가 곧 (투입되는 친구의 수 + 1. depth 가 0 부터 시작하기 때문에)와 같기 떄문에 기존에 저장해둔 현재까지의 최소 친구 수 answer 보다 dpeth + 1 가 그 이상으로 더 커지게 되면 굳이 그 쪽으로 가지치기를 할 필요가 없다. answer를 업뎃 할 수 있는 가능성이 없는 경로이기 떄문이다. 따라서 아래 코드 하나로 시간을 많이 줄일 수 있다. 근데 이 코드가 없어도 통과되긴 했다..⭐

    if (depth + 1 >= answer)
        return;
    

    

✈ 비트 연산으로 방문 체크

위 유튜브에서는 방문 체크를 배열이 아닌 int 정수로 하고 비트 연산으로 방문 체크를 한 것이다. 앞으로 나도 자주 써먹어야지 싶어 정리해둔다.

• 방문 체크 👉 방문한 외벽 자리에 대응되는 비트를 1로 바꾼다.
  • 👉 weak_visited |= (1 << next_weak_pos)
    • 점검 완료한 외벽 인덱스가 3 이라면 1 << 3은 00000001을 3 번 왼쪽으로 민 것이니 00001000이 된다. 이것과 방문 체크 변수인 weak_visited 와 OR 연산을 하면 weak_visited의 3 번째 자리가 1 이 된다. 이렇게 방문 체크를 할 수 있다.
      • 비트는 오른쪽부터 읽는다! 00001 은 4번째 자리가 방문된 것이 아닌 0번쨰 자리가 방문된 것이다.
• 모든 외벽이 방문 되었는지 검사 👉 예를들어 외벽이 6개라면 현재 방문체크 변수가 111111 과 완전히 동일한지를 봐야한다. 즉, 모든 비트가 1 인지 검사
  • 👉 weak_visited == (1 << weak.size()) - 1)
    • 외벽 개수가 총 3 개라면 모든 비트가 1 인 111 을 만드는 방법은 1 을 3 번 밀어 1000 으로 만든 후 이 값에서 1을 빼주면된다!
    • 따라서 ((1 « weak.size()) 에서 1 을 빼준 값이랑 같은지를 비교하면 된다.
• 특정 하나의 외벽이 방문 되었는지 검사 👉 외벽 자리에 대응되는 특정 자리의 비트가 1 인지를 검사.
  • 👉 weak_visited & (1 << start)
    • start 인덱스에 대응되는 ``weak_visited`의 비트가 1 인지를 보기 위해 AND 연산을 한다.
    • 점검 완료한 외벽 인덱스가 3 이라면 1 << 3은 00000001을 3 번 왼쪽으로 민 것이니 00001000이 된다. 이것과 방문 체크 변수인 weak_visited 와 AND 연산을 했을 때 결과가 FALSE 이라면 weak_visited의 해당 자리는 0 비트라는 것이고 (해당 외벽 방문 안했다는 뜻) 결과가 TRUE 라면 1 비트가 맞다는 것이다. (해당 외벽 방문 했다는 뜻)

(C++) 비트와 부분 집합 (+ STL bitset 활용)

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기