[BOJ] 백준 20209번 - 스트레이트 스위치 게임

| |
백준 온라인 저지 20209번 - 스트레이트 스위치 게임 C++ 풀이 (2020 중앙대학교 프로그래밍 경진대회 D번)


문제

어느 나라에는, 여러 큐브와 연결된 스위치를 적절한 횟수만큼 눌러 모든 큐브 위에 적힌 숫자를 동일하게 만드는 게임이 있다.

그중 스트레이트 스위치라는 게임이 있다.

스트레이트 스위치 게임은 다음의 규칙을 따른다.

  • 선분 위에 여러 개의 큐브가 일렬로 놓여 있고, 이 큐브 중 특정 큐브들과 연결된 스위치들이 여러 개 존재한다.
  • i 번 스위치를 한 번 누르면 해당 스위치와 연결된 모든 큐브 위의 숫자가 1씩 빠르게 i 번 증가해, 총 i 만큼 증가한다.
  • 큐브 위의 숫자는 0, 1, 2, 3, 4만 존재할 수 있으며 스위치를 눌러 큐브 위의 숫자가 증가하다 4를 초과하면 0으로 즉시 초기화된다.
  • 스위치를 한 번 누를 때, 반드시 단 한 개의 스위치만 누를 수 있다.
  • 같은 번호의 큐브가 한 스위치에 여러 번 연결되어있는 경우는 없다.
  • 각 스위치를 누를 수 있는 횟수의 제한은 없다.
  • 큐브 위에 쓰여 있는 모든 숫자가 동일해지는 순간, 게임은 종료된다.

이 스트레이트 스위치 게임의 국가 대표 선수인 당신은 세계 대회에서 우수한 성적을 거두기 위해 전략을 세워야 한다.

큐브의 개수와 현재 큐브 위에 쓰여 있는 숫자들, 그리고 스위치-큐브 간의 연결 정보가 주어질 때

이 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구해보자


입력

첫 번째 줄에는 큐브의 개수 N과 스위치의 개수 K가 주어진다. (1 ≤ N, K ≤ 8)

두 번째 줄에는 현재 N개의 큐브 위에 쓰여 있는 숫자 a1 a2 a3 … aN 가 한 줄에 주어진다. (0 ≤ ai ≤ 4)

세 번째 줄 부터 K+3번째 줄에는, 1번 스위치부터 K번 스위치까지 각 스위치에 연결된 큐브의 개수(Bm)와, 연결된 큐브의 번호들(bj)이 각 줄 마다 주어진다. (1 ≤ j, B ≤ N, 1 ≤ m, bj ≤ K)


출력

첫 번째 줄에 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 출력한다.

(단, 주어진 스위치들을 아무리 누르더라도 모든 큐브의 숫자를 동일하게 만들 수 없는 경우에는 -1을 출력한다.)


풀이

스위치를 누르는 최소 횟수를 구하는 문제라는 점에서 최단 거리 문제임을 알 수 있다. BFS 를 사용할 것인데, 큐브는 정수가 나열된 vector 형태의 데이터이므로 지점마다의 최단거리를 기록할 때 vector 형식을 key 로 갖는 map 자료구조를 사용해야 한다. 큐브와 스위치의 개수가 8개로 아주 작으므로 이런 방식을 사용해도 시간 안에 충분히 돌아갈 것이라고 예상할 수 있다.

그리고 약간의 구현 능력이 필요한 부분은 큐브와 스위치의 연결인데, 이는 vector 배열을 선언하여 각 인덱스마다 해당 번호의 스위치에 연결된 큐브 번호들을 넣어주면 된다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int N,K;
vector<int> sch[8];

bool allSame(vector<int>& v){
    int n = v[0];
    for(int i:v) if(n!=i) return false;
    return true;
}

vector<int> press(vector<int>& cube, int n){
    vector<int> ret = cube;

    for(int i:sch[n]){
        ret[i-1]+=n+1;
        ret[i-1]%=5;
    }

    return ret;
}

int bfs(vector<int>& init){
    map<vector<int>,int> m;
    queue<vector<int>> q;

    m[init]=0;
    q.push(init);

    while(!q.empty()){
        vector<int> cur = q.front();
        q.pop();

        int curDist = m[cur];

        if(allSame(cur)) return curDist;

        for(int i=0;i<K;i++){
            vector<int> next = press(cur,i);
            if(m.find(next)==m.end()){
                m[next]=curDist+1;
                q.push(next);
            }
        }
    }

    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>K;

    vector<int> cube(N);
    for(int& i:cube) cin>>i;

    for(int i=0;i<K;i++){
        int n; cin>>n;
        sch[i]=vector<int>(n);
        for(int& num:sch[i]) cin>>num;
    }

    cout<<bfs(cube);

    return 0;
}
0%