각 라운드마다 가위, 바위, 보를 카운팅 한 후 각 경우마다 패배자를 Check해서 1명이 남을 때까지 라운드를 진행합니다.
#include<iostream>
#include<string>
using namespace std;
string list[11];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
bool check[11] = {}; // i번째 선수가 졌으면 check[i] = true;
bool flag = false;
for (int i = 1; i <= n; i++)
cin >> list[i];
for (int i = 0; i < list[1].length(); i++) {
bool RPS[3] = {}; // R P S 나온걸체크
for (int j = 1; j <= n; j++) {
if (check[j] == true) // 이미 기존에 진사람
continue;
if (list[j][i] == 'R')
RPS[0] = true;
if (list[j][i] == 'P')
RPS[1] = true;
if (list[j][i] == 'S')
RPS[2] = true;
}
// R P S 가 다 나온 경우.
if (RPS[0] && RPS[1] && RPS[2])
continue;
// R P 가 나온 경우
if (RPS[0] && RPS[1] && !RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] == false && list[j][i] == 'R')
check[j] = true;
}
// R S 가 나온 경우
if (RPS[0] && !RPS[1] && RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] ==false && list[j][i] == 'S')
check[j] = true;
}
// P S 가 나온 경우
if (!RPS[0] && RPS[1] && RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] == false && list[j][i] == 'P')
check[j] = true;
}
int count = 0, index = 0;
for (int j = 1; j <= n; j++) {
if (check[j] == false) {
count++;
index = j;
}
}
if (count == 1){
cout << index << '\n';
flag = true;
break;
}
}
if (!flag)
cout << 0 << '\n';
}
}
1. A에서 시작해서 명령어 D / S / L / R 을 한 숫자가 아직 방문하지 않은 숫자라면 queue에 담아 가며 B가 나올 때까지 BFS 탐색을 진행한다. 이때, int path[10000], char answer[10001] 을 이용해서 방문 경로를 저장한다.
2. B에서 다시 방문 경로를 역 탐색하며 출력해준다.
#include<iostream>
#include<queue>
using namespace std;
char DSLR[5] = "DSLR";
void BFS(int, int);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int A, B;
cin >> A >> B;
BFS(A,B);
}
}
void BFS(int A, int B) {
bool check[10000] = {};
int npath[10000] = {};
char cpath[10001] = {};
queue<int> q;
q.push(A);
check[A] = true;
while (!q.empty()) {
int x = q.front(); q.pop();
if (x == B) {
vector<char>answer;
while (x != A) {
answer.push_back(cpath[x]);
x = npath[x];
}
int length = (int)answer.size();
for (int i = 0; i < length; i++)
cout << answer[length - 1 - i];
cout << '\n';
return;
}
int list[4] = { (2 * x) % 10000, x - 1, (x % 1000) * 10 + x / 1000, (x % 10) * 1000 + x / 10 };
if (list[1] < 0)
list[1] = 9999;
for (int i = 0; i < 4; i++) {
if (!check[list[i]]) { // 지금 가려는 곳이 방문한 곳이 아니라면
q.push(list[i]);
check[list[i]] = true;
npath[list[i]] = x;
cpath[list[i]] = DSLR[i];
}
}
}
}
