#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
int l_prev = 0, r_prev = 0;
int l, r;
int fun_score = 0;
for (int i = 0; i < T; i++) {
cin >> l >> r;
if (i > 0) {
// 재미도 계산
if (l != 0 && l == l_prev) {
fun_score++;
}
if (r != 0 && r == r_prev) {
fun_score++;
}
}
if (r != 0 && l == r) {
fun_score++;
}
// 현재 상태를 이전 상태로 업데이트
l_prev = l;
r_prev = r;
}
cout << fun_score << endl;
return 0;
}
우선 이 문제에서 주목해야 될 포인트는 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;
}
