문제
혹시 마지막으로 엠티를 간 것이 언제인가? 엠티를 안간지 꽤 오래됐다면 요즘 유행하는 인싸들의 가위바위보를 모를 것이다. 요즘 인싸들은 엠티에서 평범한 가위바위보를 시시하다는 이유로 더 이상 취급하지 않는다. 대신 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀을 한다. 이 게임의 명칭이 다소 긴 관계로 문제 내에서는 전체 명칭을 적는 대신 이 게임의 또 다른 이름인 인싸 가위바위보로 부르겠다. 인싸 가위바위보는 평범한 가위바위보와 같이 각 손동작간의 상성이 정해져있다.
인싸 가위바위보는 평범한 가위바위보보다 흥미진진하고 재밌지만 3명 이상이 경기를 할 때 누가 이기고 누가 졌는지를 빠르게 알기 힘들다는 단점이 있다. 그렇기에 3명 이상의 사람들 사이에서 인싸 가위바위보를 할 때는 모두가 동시에 경기를 진행하는 대신 일대일 경기를 여러 번 진행해 누가 우승했는지 판단한다. 3명이서 인싸 가위바위보를 할 때의 우승자를 정하기 위한 구체적인 방식은 아래와 같다. 편의상 참가자 3명을 A, B, C라고 하자.
- A, B, C는 게임 시작 전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의한다. 경기 진행 순서가 A, B, C라고 가정하자.
- 먼저 A와 B가 경기를 진행해 승자를 결정한다. 만약 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주한다. 즉 A와 B가 같은 손동작을 내면 B의 승리, A와 C가 같은 손동작을 내면 C의 승리, B와 C가 같은 손동작을 내면 C의 승리이다.
- 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다.
- 특정 사람이 미리 합의된 승수를 달성할 때 까지 3을 반복한다.
- 합의된 승수를 최초로 달성한 사람이 우승한다.
밑의 표는 침, 펄, 풍 세 사람이 인싸 가위바위보를 진행하는 예시이다. 우승을 위해 필요한 승수는 3승이고 침, 펄, 풍 순서로 경기를 진행한다.
인싸 가위바위보 결과 풍이 제일 먼저 3승에 도달했으므로 우승자는 풍이다. 1라운드, 3라운드에서 두 사람이 같은 손동작을 냈을 때 경기 진행 순서상 뒤인 사람이 승리하는 것을 확인할 수 있다.
컴퓨터공학과 새내기 지우는 첫 엠티에서 친구 경희, 민호와 인싸 가위바위보를 할 생각에 굉장히 신나있다. 지우는 경희와 민호의 행동 패턴을 빅데이터로 분석해 인싸 가위바위보를 하는 중 경희와 민호의 차례가 왔을 때 이들이 낼 손동작의 순서를 정확히 알고 있다. 그래서 마음만 먹으면 전승 우승이 가능하지만 경기를 흥미진진하게 이끌기 위해 인싸 가위바위보를 할 때 모든 손동작을 다르게 내고 싶어한다. 지우의 즐거운 대학생활을 위해 인싸 가위바위보의 상성표와 경희, 민호가 낼 손동작의 순서가 주어졌을 때 지우가 모든 손동작을 다르게 내어 우승할 수 있는지 판단하는 프로그램을 만들자. 경기 진행 순서는 지우, 경희, 민호 순으로 정해져있다.
출력
첫째 줄에 지우, 경희, 민호 순으로 경기를 진행할 때 지우가 모든 손동작을 다르게 내어 우승할 수 있으면 1을, 그렇지 않으면 0을 출력한다.
풀이
처음 문제를 보고 '모든 종류의 손동작을 다르게 내어, 우승할 수 있는지' 여부를 판단하는 줄 알았습니다.
그러나 질문게시판을 통해 '한번 낸 손동작을 다시 내지 않고 우승할 수 있는지'여부를 판단하는 문제였습니다.
먼저 dfs를 통해 저마다 다른 손동작 N개의 순열을 만듭니다.
물론 경희나 민호는 20경기에서 낼 손동작의 순서를 입력받지만
N + 1개의 순열을 만드는 순간 이미 한번 냈던 손동작을 다시 한번 내는수밖에 없습니다.
void dfs(int x) {
if (x >= N) {
for (int i = 0; i <= 3; i++) {
index[i] = 0; // i번 선수가 낼 순서 인덱스
winCnt[i] = 0; // i번 선수의 승리 횟수
}
int first = 1; // 가위바위보를 하는 사람 1, 초깃값 : 1(지우)
int second = 2; // 가위바위보를 하는 사람 2, 초깃값 : 2(경희)
while (true) {
int next = getNext(first, second);
int winner = game(first, second);
if(check()) break;
first = winner;
second = next;
}
if (possible) {
cout << 1;
return;
}
}
~ 생략
} index[i]에는 i번 선수가 낼 순서 인덱스를 의미합니다.
예를 들어 index[2] = 3인 경우, 2번 선수(경희)가 낼 손 동작 인덱스가 3이라는 뜻이며 예제 테스트 케이스에서는 2번 손동작을 의미합니다.
winCnt[i]에는 i번 선수의 승리 횟수가 기록됩니다.
다시 경기 규칙을 살펴보고 규칙대로 구현해보도록 하겠습니다.
- A, B, C는 게임 시작 전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의한다. 경기 진행 순서가 A, B, C라고 가정하자.
- 먼저 A와 B가 경기를 진행해 승자를 결정한다. 만약 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주한다. 즉 A와 B가 같은 손동작을 내면 B의 승리, A와 C가 같은 손동작을 내면 C의 승리, B와 C가 같은 손동작을 내면 C의 승리이다.
- 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다.
- 특정 사람이 미리 합의된 승수를 달성할 때 까지 3을 반복한다.
- 합의된 승수를 최초로 달성한 사람이 우승한다.
int first = 1; // 가위바위보를 하는 사람 1, 초깃값 : 1(지우)
int second = 2; // 가위바위보를 하는 사람 2, 초깃값 : 2(경희)
while (true) {
int next = getNext(first, second);
int winner = game(first, second);
if(check()) break;
first = winner;
second = next;
}
game() 함수를 통해 승자를 구합니다. 이번판의 승자는, 이번판에 참여하지 않은 참가자와 다음판에서 승부를 겨룹니다. getNext() 함수를 통해 이번판에 참여하지 않은 참가자를 구합니다. check() 함수를 통해 K번의 승리한 사람이 있는지, 모든 손동작을 냈음에도 이기지 못했는지 등등 확인합니다.
check() 함수를 살펴보도록 하겠습니다.
bool check() {
bool canBreak = false;
// 경희나 민호가 먼저 승수에 도달한 경우
if (winCnt[2] >= K || winCnt[3] >= K) {
canBreak = true;
}
// 지우가 먼저 승수에 도달한 경우
else if (winCnt[1] >= K) {
possible = true;
canBreak = true;
}
// 지우가 모든 손 동작을 다 낸 경우
else if (index[1] >= N) {
canBreak = true;
}
return canBreak;
}경희나 민호가 먼저 승수에 도달한 경우 더이상 진행하지 않고 끝내버리기 위해 flag 값을 수정했습니다.저같은 경우 오랜시간 헤메었던 부분이 else if문의 순서였습니다.
처음에는 지우가 모든 손 동작을 다 낸 경우를 지우가 먼저 승수에 도달한 경우보다 먼저 검사하였습니다.index가 0부터 시작하기 때문에 index가 N-1인 경우가 모든 손동작을 다 낸 상황이라고 생각했고index가 N인 경우 이미 범위를 초과하기 때문에 더이상 진행하지 않고 끝내버리기 위해 flag 값을 수정했었습니다.
(1) 게임을 진행하고(승수 update) (2) check() 함수 실행하고 (3) index가 올라간다면 위 로직이 알맞게 돌아가겠지만 제 케이스에서는(1) 게임을 진행하고(승수 update 및 index 증가) (2) check() 함수를 실행하기 때문에index가 N인 경우라도 체크를 해주어야 했습니다.
앞으로는 언제 index가 증가하느냐에 대해 좀 더 깊은 고민을 해야겠습니다.
전체 소스코드는 아래와 같습니다.
#include <iostream>
using namespace std;
bool possible = false;
int N, K; // N : 손동작 수, K : 우승 수
int A[15][15];
int orders[4][25];
int winCnt[4];
bool isUsing[25];
int index[4] = { 0, };
// 경기에 참여하지 않은 사람을 반환합니다.
int getNext(int a, int b) {
if ((a == 1 && b == 2) || (a == 2 && b == 1)) {
return 3;
}
else if ((a == 2 && b == 3) || (a == 3 && b == 2)) {
return 1;
}
else
return 2;
}
// 앞사람이 뒷사람을 이기면 2, 비기면 1, 지면 0을 return한다.
int doesWin(int a, int b) {
return A[a][b];
}
int game(int player1, int player2) {
int player1Idx = index[player1]++; // 첫번째 선수의 게임 순서를 의미
int player2Idx = index[player2]++; // 두번째 선수의 게임 순서를 의미
int result = doesWin(orders[player1][player1Idx], orders[player2][player2Idx]);
if (result == 2) { // 1번이 2번을 이김
winCnt[player1]++;
return player1;
}
else if (result == 1) { // 비김
// 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주
if (player1 > player2) {
winCnt[player1]++;
return player1;
}
else {
winCnt[player2]++;
return player2;
}
}
else if (result == 0) { // 2번이 1번을 이김
winCnt[player2]++;
return player2;
}
}
bool check() {
bool canBreak = false;
// 경희나 민호가 먼저 승수에 도달한 경우
if (winCnt[2] >= K || winCnt[3] >= K) {
canBreak = true;
}
// 지우가 먼저 승수에 도달한 경우
else if (winCnt[1] >= K) {
possible = true;
canBreak = true;
}
// 지우가 모든 손 동작을 다 낸 경우
else if (index[1] >= N) {
canBreak = true;
}
return canBreak;
}
void dfs(int x) {
if (x >= N) {
for (int i = 0; i <= 3; i++) {
index[i] = 0;
winCnt[i] = 0;
}
int first = 1; // 가위바위보를 하는 사람 1, 초깃값 : 1(지우)
int second = 2; // 가위바위보를 하는 사람 2, 초깃값 : 2(경희)
while (true) {
int next = getNext(first, second);
int winner = game(first, second);
if(check()) break;
first = winner;
second = next;
}
if (possible) {
cout << 1;
return;
}
}
else {
for (int i = 1; i <= N; i++) {
if (isUsing[i] == false) {
isUsing[i] = true;
orders[1][x] = i;
dfs(x + 1);
if (possible) return;
isUsing[i] = false;
orders[1][x] = 0;
}
}
}
}
void init() {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> A[i][j];
}
}
for (int i = 0; i < 20; i++) {
cin >> orders[2][i];
}
for (int i = 0; i < 20; i++) {
cin >> orders[3][i];
}
}
int main() {
init();
/* 저마다 다른 손모양 N개의 순열을 만듭니다.
이는 지우가 낼 손동작의 순서가 됩니다. */
dfs(0);
if (!possible) {
cout << 0;
}
return 0;
}
'Algorithm' 카테고리의 다른 글
| [C++][백준] 구슬 탈출 2(13460) (0) | 2021.04.16 |
|---|---|
| [C++][백준] 마법사 상어와 토네이도(20057) (1) | 2021.04.15 |
| [C++][백준] 다리 만들기2(17472) (0) | 2021.04.06 |
| [C++][백준] 다리 만들기(2146) (0) | 2021.03.23 |
| [C++][백준] 문명(14868) (0) | 2021.03.23 |
