문제 링크

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

 

16986번: 인싸들의 가위바위보

두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되

www.acmicpc.net

문제

혹시 마지막으로 엠티를 간 것이 언제인가? 엠티를 안간지 꽤 오래됐다면 요즘 유행하는 인싸들의 가위바위보를 모를 것이다. 요즘 인싸들은 엠티에서 평범한 가위바위보를 시시하다는 이유로 더 이상 취급하지 않는다. 대신 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀을 한다. 이 게임의 명칭이 다소 긴 관계로 문제 내에서는 전체 명칭을 적는 대신 이 게임의 또 다른 이름인 인싸 가위바위보로 부르겠다. 인싸 가위바위보는 평범한 가위바위보와 같이 각 손동작간의 상성이 정해져 있다. 

인싸 가위바위보는 평범한 가위바위보보다 흥미진진하고 재밌지만 3명 이상이 경기를 할 때 누가 이기고 누가 졌는지를 빠르게 알기 힘들다는 단점이 있다. 그렇기에 3명 이상의 사람들 사이에서 인싸 가위바위보를 할 때는 모두가 동시에 경기를 진행하는 대신 일대일 경기를 여러 번 진행해 누가 우승했는지 판단한다. 3명이서 인싸 가위바위보를 할 때의 우승자를 정하기 위한 구체적인 방식은 아래와 같다. 편의상 참가자 3명을 A, B, C라고 하자.

  1. A, B, C는 게임 시작 전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의한다. 경기 진행 순서가 A, B, C라고 가정하자.
  2. 먼저 A와 B가 경기를 진행해 승자를 결정한다. 만약 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주한다. 즉 A와 B가 같은 손동작을 내면 B의 승리, A와 C가 같은 손동작을 내면 C의 승리, B와 C가 같은 손동작을 내면 C의 승리이다. 
  3. 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다.
  4. 특정 사람이 미리 합의된 승수를 달성할 때 까지 3을 반복한다.
  5. 합의된 승수를 최초로 달성한 사람이 우승한다.

밑의 표는 침, 펄, 풍 세 사람이 인싸 가위바위보를 진행하는 예시이다. 우승을 위해 필요한 승수는 3승이고 침, 펄, 풍 순서로 경기를 진행한다.

인싸 가위바위보 결과 풍이 제일 먼저 3승에 도달했으므로 우승자는 풍이다. 1라운드, 3라운드에서 두 사람이 같은 손동작을 냈을 때 경기 진행 순서상 뒤인 사람이 승리하는 것을 확인할 수 있다.

컴퓨터공학과 새내기 지우는 첫 엠티에서 친구 경희, 민호와 인싸 가위바위보를 할 생각에 굉장히 신나있다. 지우는 경희와 민호의 행동 패턴을 빅데이터로 분석해 인싸 가위바위보를 하는 중 경희와 민호의 차례가 왔을 때 이들이 낼 손동작의 순서를 정확히 알고 있다. 그래서 마음만 먹으면 전승 우승이 가능하지만 경기를 흥미진진하게 이끌기 위해 인싸 가위바위보를 할 때 모든 손동작을 다르게 내고 싶어한다. 지우의 즐거운 대학생활을 위해 인싸 가위바위보의 상성표와 경희, 민호가 낼 손동작의 순서가 주어졌을 때 지우가 모든 손동작을 다르게 내어 우승할 수 있는지 판단하는 프로그램을 만들자. 경기 진행 순서는 지우, 경희, 민호 순으로 정해져있다.

입력

첫째 줄에 인싸 가위바위보의 손동작 수를 나타내는 N(1 ≤ N ≤ 9)과 우승을 위해 필요한 승수 K(1 ≤ K ≤ 6)가 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에 대해 상성에 대한 정보 Ai,j가 주어진다. i+1번째 줄에는 N개의 정수 Ai,1, Ai,2, Ai,3, ..., Ai,N이 한 칸의 빈칸을 사이에 두고 주어진다. Ai,j가 2일 경우에는 i번 손동작이 j번 손동작을 이긴다는 의미이고, 1일 경우에는 비긴다는 의미이고, 0일 경우에는 진다는 의미이다. Ai,i = 1이고, i ≠ j일 때 Ai,j ≠ 1임이 보장된다. 또한 Ai,j가 2일 경우에는 Aj,i가 0이고, Ai,j가 0일 경우에는 Aj,i가 2임이 보장된다.

그 다음 줄에는 경희가 앞으로 자신이 참여하는 20경기에서 낼 손동작의 순서가 한 칸의 빈칸을 사이에 두고 주어진다. 손동작의 번호는 1 이상 N 이하이다.

그 다음 줄에는 민호가 앞으로 자신이 참여하는 20경기에서 낼 손동작의 순서가 한 칸의 빈칸을 사이에 두고 주어진다. 마찬가지로 손동작의 번호는 1 이상 N 이하이다.

출력

첫째 줄에 지우, 경희, 민호 순으로 경기를 진행할 때 지우가 모든 손동작을 다르게 내어 우승할 수 있으면 1을, 그렇지 않으면 0을 출력한다.

예제 입력 1

3 2
1 0 2
2 1 0
0 2 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

예제 출력 1

1

예제 입력 2

3 1
1 2 2
0 1 2
0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 2 1 3 2 1 1 2 3 3 2 2 3 2 1 3 3 2 1 1

예제 출력 2

0

예제 입력 3

4 5
1 0 2 0
2 1 0 2
0 2 1 2
2 0 0 1
1 3 2 1 3 2 2 2 2 1 3 1 3 2 1 3 2 2 2 2
2 3 3 3 1 1 3 1 3 2 1 3 2 2 2 2 1 3 1 2

예제 출력 3

0

예제 입력 4

9 6
1 2 2 0 0 2 2 0 2
0 1 0 2 0 2 0 2 2
0 2 1 0 0 0 0 0 2
2 0 2 1 0 0 2 2 2
2 2 2 2 1 0 2 2 2
0 0 2 2 2 1 2 2 0
0 2 2 0 0 0 1 2 0
2 0 2 0 0 0 0 1 0
0 0 0 0 0 2 2 2 1
4 8 6 1 2 3 3 7 6 4 4 9 9 3 6 7 6 4 1 1
3 8 9 7 9 8 6 3 8 7 1 6 2 3 6 5 8 5 1 8

예제 출력 4

1

예제 입력 5

4 2
1 0 0 0
2 1 2 0
2 0 1 0
2 2 2 1
2 2 3 1 1 3 3 2 2 1 4 1 1 3 3 1 1 1 1 4
1 4 4 2 1 3 1 2 3 4 2 2 3 4 4 2 4 3 1 3

예제 출력 5

1

예제 입력 6

9 6
1 0 2 2 2 2 2 2 0
2 1 0 2 0 2 0 2 2
0 2 1 2 2 0 2 2 0
0 0 0 1 2 2 2 2 0
0 2 0 0 1 2 2 0 0
0 0 2 0 0 1 0 0 2
0 2 0 0 0 2 1 0 0
0 0 0 0 2 2 2 1 2
2 0 2 2 2 0 2 0 1
6 5 8 9 6 1 8 2 1 7 9 5 1 3 4 9 2 3 1 1
2 2 9 9 4 5 9 7 2 7 7 3 1 7 6 6 5 4 2 6

예제 출력 6

1

예제 입력 7

5 2
1 0 0 0 2
2 1 0 0 2
2 2 1 2 0
2 2 0 1 0
0 0 2 2 1
3 5 1 5 2 2 4 5 4 4 1 5 4 3 2 4 3 4 3 4
3 1 3 4 1 1 1 1 3 1 2 1 1 1 3 3 4 1 1 3

예제 출력 7

0

예제 입력 8

9 5
1 2 2 0 0 2 0 2 2
0 1 0 0 2 2 2 0 0
0 2 1 0 0 0 2 0 0
2 2 2 1 2 2 2 2 2
2 0 2 0 1 2 0 0 2
0 0 2 0 0 1 0 0 0
2 0 0 0 2 2 1 0 0
0 2 2 0 2 2 2 1 0
0 2 2 0 0 2 2 2 1
4 7 4 4 1 8 4 3 5 4 4 9 7 1 9 9 6 9 8 8
1 3 5 5 7 6 1 4 8 8 2 9 9 7 9 1 8 3 9 7

예제 출력 8

0

알고리즘 분류

  • 구현
  • 브루트포스 알고리즘
  • 백트래킹

풀이

백트래킹을 사용하여 구현하는 것에는 어려움은 없었으나, 문제를 완벽하게 이해하는 것이 까다로웠다.

Depth번째 게임에서 경희 혹은 민호가 Depth번째 손동작을 내는 것이 아니라, 무슨 손동작을 내야 하는지 각각 결정되는 것이었다. 예제 8을 보면, 1번째 게임에서 경희가 4를 내고 민호와 2번째 게임을 진행한다고 할 때, 경희가 7을 내고 민호가 3을 내는 것이 아닌 경희가 7을 내고 민호가 1을 낸다는 것이다. 그렇게 코드를 수정하니 AC를 받았다.

나머지 부분은 문제에서 제시한 조건대로 구현한다면 어렵지 않을 것이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 15
#define INF 1e9

using namespace std;
int N, K;
int A[MAX][MAX]; // 가위바위보 게임의 상성
int MAP[3][20]; // A번 사람이 B번째로 낼 손동작
int visited[MAX]; // A번 손동작을 냈는지 안 냈는지의 여부
int Win[3]; // A번 사람이 이긴 횟수
int Player_Phase[3]; // A번 사람이 낸 손동작의 횟수
bool answer = false;

bool Check_All() { // 모든 손동작을 다 냈다면 true를 return
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			return false;
		}
	}
	return true;
}

void Play_Game(int Depth, int Winner, int Turn) {
	if (answer) {
		// answer가 true가 되었다는 것은 더 이상 남은 경우의 수를 따질 필요가 없다는 것이다.
		return;
	}
	if (Depth == 20) {
		// 가위바위보 게임의 최대 횟수는 20회이다.
		return;
	}
	if (Check_All() && (Win[0] < K)) {
		// 모든 손동작을 다 냈는데 이긴 횟수가 K번이 안 된다면 게임을 더 진행할 필요가 없다.
		return;
	}
	if (Win[0] == K) {
		if ((Win[1] < K) && (Win[2] < K)) {
			// 지우가 K번 이겼을 때, 경희, 민호가 K번 미만으로 이겼다면 지우의 우승이다.
			answer = true;
		}
		return;
	}
	if ((Win[1] == K) || (Win[2] == K)) {
		if (Win[0] < K) {
			// 경희나 민호가 먼저 K번 이기면 지우는 우승에 실패한 것이므로 게임을 더 진행할 필요가 없다.
			return;
		}
	}
	int First = Winner; // 직전 게임 우승자. 첫 게임은 지우
	int Second = Turn; // 직전에 게임에 참여하지 않은 사람, 첫 게임은 경희
	// 지우가 게임에 참여했을 경우
	if ((First == 0) && (Second != 0)) {
		int next_Turn;
		if (Second == 1) {
			next_Turn = 2;
		}
		else if (Second == 2) {
			next_Turn = 1;
		}
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				int First_Card = i; // 지우가 고를 손동작(1~N까지)
				int Second_Card = MAP[Second][Player_Phase[Second]]; // 상대방이 낼 손동작
				if (A[First_Card][Second_Card] == 0) {
					Win[Second]++; // 이긴 사람의 이긴 횟수 증가
					Player_Phase[Second]++; // 지우의 상대가 낼 손동작의 순번 증가
					visited[i] = true; // i번째 손동작을 내었다 -> true
					Play_Game(Depth + 1, Second, next_Turn); // 재귀
					visited[i] = false;
					Player_Phase[Second]--;
					Win[Second]--;
				}
				else if (A[First_Card][Second_Card] == 1) {
					int Cur_Winner = max(First, Second);
					Win[Cur_Winner]++;
					Player_Phase[Second]++;
					visited[i] = true;
					Play_Game(Depth + 1, Cur_Winner, next_Turn);
					visited[i] = false;
					Player_Phase[Second]--;
					Win[Cur_Winner]--;
				}
				else if (A[First_Card][Second_Card] == 2) {
					Win[First]++;
					Player_Phase[Second]++;
					visited[i] = true;
					Play_Game(Depth + 1, First, next_Turn);
					visited[i] = false;
					Player_Phase[Second]--;
					Win[First]--;
				}
			}
		}
	}
	else if ((First != 0) && (Second == 0)) {
		int next_Turn;
		if (First == 1) {
			next_Turn = 2;
		}
		else if (First == 2) {
			next_Turn = 1;
		}
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				int First_Card = MAP[First][Player_Phase[First]];
				int Second_Card = i;
				if (A[First_Card][Second_Card] == 0) {
					Win[Second]++;
					Player_Phase[First]++;
					visited[i] = true;
					Play_Game(Depth + 1, Second, next_Turn);
					visited[i] = false;
					Player_Phase[First]--;
					Win[Second]--;
				}
				else if (A[First_Card][Second_Card] == 1) {
					int Cur_Winner = max(First, Second);
					Win[Cur_Winner]++;
					Player_Phase[First]++;
					visited[i] = true;
					Play_Game(Depth + 1, Cur_Winner, next_Turn);
					visited[i] = false;
					Player_Phase[First]--;
					Win[Cur_Winner]--;
				}
				else if (A[First_Card][Second_Card] == 2) {
					Win[First]++;
					Player_Phase[First]++;
					visited[i] = true;
					Play_Game(Depth + 1, First, next_Turn);
					visited[i] = false;
					Player_Phase[First]--;
					Win[First]--;
				}
			}
		}
	}
	// 지우가 게임에 참여하지 않았을 때
	else if ((First != 0) && (Second != 0)) {
		int First_Card = MAP[First][Player_Phase[First]];
		int Second_Card = MAP[Second][Player_Phase[Second]];
		if (A[First_Card][Second_Card] == 0) {
			Win[Second]++;
			Player_Phase[First]++;
			Player_Phase[Second]++;
			Play_Game(Depth + 1, Second, 0); // 다음 차례는 무조건 지우
			Player_Phase[Second]--;
			Player_Phase[First]--;
			Win[Second]--;
		}
		else if (A[First_Card][Second_Card] == 1) {
			int Cur_Winner = max(First, Second);
			Win[Cur_Winner]++;
			Player_Phase[First]++;
			Player_Phase[Second]++;
			Play_Game(Depth + 1, Cur_Winner, 0);
			Player_Phase[Second]--;
			Player_Phase[First]--;
			Win[Cur_Winner]--;
		}
		else if (A[First_Card][Second_Card] == 2) {
			Win[First]++;
			Player_Phase[First]++;
			Player_Phase[Second]++;
			Play_Game(Depth + 1, First, 0);
			Player_Phase[Second]--;
			Player_Phase[First]--;
			Win[First]--;
		}
	}
}

int main() {
	FIRST
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			/*
				가위바위보의 상성. A[i][j]가 2라면 i를 낸 쪽이 이겼다는 뜻이고,
				1이라면 경기 진행 순서가 늦는 쪽이 이기고,
				0이라면 j를 낸 쪽이 이겼다는 뜻이다.
			*/
			cin >> A[i][j];
		}
	}
	for (int i = 1; i < 3; i++) {
		for (int j = 0; j < 20; j++) {
			// 지우를 0, 경희를 1, 민호를 2라고 봤을 때 경희와 민호가 낼 손동작 20가지를 배열에 저장한다.
			cin >> MAP[i][j];
		}
	}
	if (N >= K) {
		/*
			K가 N보다 크다면, N가지 손동작을 1번씩 냈음에도 불구하고
			이겨야 하는 횟수가 더 남은 것이기 때문에,
			무조건 답은 0이 나와야 한다.
			따라서 N이 K 이상일 경우만 따진다.
		*/
		Play_Game(0, 0, 1); // 재귀를 이용하여 모든 경우의 수를 따진다.
	}
	cout << answer << "\n";

	return 0;
}

'BOJ > Gold' 카테고리의 다른 글

[BOJ/Gold 3] 백준 18808 스티커 붙이기(C++)  (0) 2022.01.13
[BOJ/Gold 3] 백준 17822 원판 돌리기(C++)  (0) 2022.01.13
[BOJ/Gold 3] 백준 14676 영우는 사기꾼?(C++)  (0) 2022.01.12
[BOJ/Gold 3] 백준 13168 내일로 여행(C++)  (0) 2022.01.12
[BOJ/Gold 3] 백준 12764 싸지방에 간 준하(C++)  (0) 2022.01.11

티스토리툴바