백준 20209번 스트레이트 스위치 게임 [C++]

https://www.acmicpc.net/problem/20209

 

 

 

 

 

#문제 간단 정리

브루트포스 완전탐색을 활용하자

bfs 를 활용하면 된다

 

 

#문제 해결 방법

 

일단 문제가 좀 설명이 길기 때문에 이해하기 좀 걸릴 수가 있다.

 

우선 이 문제에서 주목해야 될 포인트는 4가 넘어가면 5로 나눈 값으로 큐브값을 유지한다는것이다.

 

그렇다면 우리는 스위치의 개수도 8개로 가짓수가 적고

계속해서 5로 나눈다면 같은 상태가 반복된다는 걸 알 수 있다.

이부분에서 전체 가짓수가 적다는걸 파악한다

 

여기서 같은 스위치를 대략 최대 4번정도 누른다면 원래 상태로 되돌아 올 수 있다는 걸 관찰 할 수 있고

각 스위치 하나마다 최대 5가지의 상태가 파생되니까

5^k 가 총 가짓수인걸 파악할 수 있다.

 

그렇다면 중복상태를 뛰어넘어서 완전탐색을 하면 되겟다는 생각이 든다. (가짓수가 적으니까)

 

-> 여기서 중복 제거를 위해서 맵이나 셋으로 중복 상태를 관리하고

-> 완전탐색은 최소 거리를 찾아야되기 때문에 bfs 가 적절하다는 생각이 든다.

 

 

 

그렇다면 이제 구현할 차례,

유의할점은 애초에 주어진 상태가 전부 같은 숫자로 주어진 

정답 상태로 초기에 주어질 수 있음만 유의하도록 하자.

 

자세한 구현은 코드보고 이해하도록 하자

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

// 모든 큐브의 숫자가 동일한지 확인하는 함수
bool equal(vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] != vec[0]) {
            return false;
        }
    }
    return true;
}

int main() {
    
    int n, k;
    cin >> n >> k;
    
    vector<int> cubes;
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        cubes.push_back(input);
    }
    
    vector<vector<int>> switches(k);
    for (int i = 0; i < k; i++) {
        int input;
        cin >> input;

        for (int j = 0; j < input; j++) {
            int input2; cin >> input2;
            switches[i].push_back(input2-1);
        }

    }

    set<vector<int>> cubeSet;


    //큐브상태,횟수
    queue<pair<vector<int>,int>> q;
    q.push({ cubes,0 });
    cubeSet.insert(cubes);

    while (!q.empty()) {

        vector<int> front = q.front().first;
        int seq = q.front().second;
        q.pop();
        if (equal(front)) {
            cout << seq  << '\n';
            return 0;
        }
         
        for (int i = 0; i < k; i++) {
            vector<int> next = front;
            for (auto a : switches[i]) {
                next[a] += i+1;
                if (next[a] > 4) {
                    next[a] %= 5;
                }
            }
            if (cubeSet.find(next) == cubeSet.end()) {
                cubeSet.insert(next);
                q.push({ next,seq + 1 });
            }

        }

    }

    cout << -1 << '\n';
    

    return 0;
}

 

 

//주석달린 버전

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

// 모든 큐브의 숫자가 동일한지 확인하는 함수
bool equal(vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] != vec[0]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> cubes(n);
    for (int i = 0; i < n; i++) {
        cin >> cubes[i];
    }
    
    vector<vector<int>> switches(k);
    for (int i = 0; i < k; i++) {
        int m;
        cin >> m;
        switches[i].resize(m);
        for (int j = 0; j < m; j++) {
            cin >> switches[i][j];
            switches[i][j]--; // 1-based index를 0-based index로 변환
        }
    }

    // 중복 상태 관리를 위한 set
    set<vector<int>> visited;

    // 큐브 상태와 스위치를 누른 횟수를 저장할 큐
    queue<pair<vector<int>, int>> q;
    q.push({cubes, 0});
    visited.insert(cubes);

    while (!q.empty()) {
        vector<int> current = q.front().first;
        int moves = q.front().second;
        q.pop();

        // 모든 큐브의 숫자가 동일하면 정답 출력 후 종료
        if (equal(current)) {
            cout << moves << endl;
            return 0;
        }

        // 각 스위치를 한번씩 눌러보는 과정
        for (int i = 0; i < k; i++) {
            vector<int> next = current;
            for (int idx : switches[i]) {
                next[idx] = (next[idx] + (i + 1)) % 5; // 스위치에 따라 숫자 변경
            }

            // 이미 방문한 상태가 아니면 큐와 set에 추가
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push({next, moves + 1});
            }
        }
    }

    // 모든 경우를 탐색했음에도 정답을 찾지 못한 경우
    cout << -1 << endl;
    return 0;
}