[BOJ/Gold 4] 백준 16722 결! 합!(C++)

문제 링크

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

16722번: 결! 합!

문제

 

‘결! 합!’ 게임은 위의 그림과 같이 도형의 모양, 도형의 색, 배경색 세 가지 속성이 각각 다르게 조합된 27장의 그림들 중 선택된 아홉 장의 그림들로 진행된다. 도형의 모양으로는 {동그라미, 세모, 네모}, 도형의 색으로는 {노란색, 빨간색, 파란색}, 배경색으로는 {회색, 흰색, 검은색}이 존재한다. 아홉 장의 그림들의 세 가지 속성이 주어지면 게임의 플레이어는 ‘합’이 되는 세 장의 그림을 찾아야한다. ‘합’이란 그림의 세 가지 속성이 모두 같거나 모두 다른 세 장의 그림 조합을 의미한다. 

예를 들어, 위 예시 1에 주어진 세 장의 그림은 도형의 모양이 모두 같고 도형의 색이 모두 다르고 배경색이 모두 같기 때문에 세 속성 전부가 모두 같거나 모두 다르므로 ‘합’을 이룬다. 그러나 예시 2에 주어진 세 장의 그림은 배경색이 모두 다르고 도형의 모양도 모두 다르지만 도형의 색은 모두 다르지도 모두 같지도 않기 때문에 ‘합’을 이루지 않는다.

‘결! 합!’ 게임은 초기점수로 0점을 가지고 시작하며 플레이어가 점수를 얻을 수 있는 행동은 다음 두 가지가 있다.

• ‘합’ 외치기: ‘합’이라고 생각되는 서로 다른 그림 세 장의 번호를 외친다. 외친 번호의 그림 세 장이 ‘합’을 이루면서 이전에 외친 적이 없는 그림 조합이라면 +1점을, 아니라면 -1점을 획득한다.
• ‘결’ 외치기: 아홉 장의 그림으로 조합 가능한 '합'들 중 외치지 않은 ‘합’이 더 이상 없다고 생각될 경우 ‘결’을 외친다. 실제로 외치지 않은 ‘합’ 이 없고 ‘결’을 통해 +3점을 얻은 적이 없다면 +3점을, 아니라면 -1점을 획득한다.

게임에 사용될 아홉 장의 그림의 속성들과 플레이어의 게임 기록이 주어졌을 때, 플레이어의 최종 점수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄부터 아홉 줄에 걸쳐 i(1 ≤ i ≤ 9)번 그림의 도형의 모양, 도형의 색, 배경색을 나타나는 Si, Ci, Bi가 주어진다.

Si는 {“CIRCLE”, “TRIANGLE”, ”SQUARE”}, Ci는 {“YELLOW”, “RED”, “BLUE”}, Bi는 {“GRAY”, “WHITE”, “BLACK”} 중 하나이다. 각 속성 사이에는 공백이 하나 주어진다.
열 번째 줄에 플레이어의 게임 기록의 수 n(1 ≤ n ≤ 100)이 주어지고 다음 줄부터 n줄에 걸쳐 다음 두 가지 입력 중 하나가 주어진다.

• H a b c : 플레이어가 ‘합’이라고 생각되는 서로 다른 그림의 번호 a, b, c를 외친 입력이다. (1 ≤ a, b, c ≤ 9)
• G : 플레이어가 ‘결’을 외친 입력이다.

출력

첫 번째 줄에 플레이어의 최종 점수를 출력한다.

예제 입력 1

CIRCLE YELLOW GRAY
CIRCLE RED BLACK
CIRCLE RED GRAY
CIRCLE YELLOW BLACK
CIRCLE RED WHITE
CIRCLE BLUE BLACK
SQUARE YELLOW GRAY
SQUARE BLUE GRAY
TRIANGLE BLUE WHITE
9
H 1 6 5
H 7 8 9
H 2 3 5
H 1 5 6
H 6 8 9
G
H 2 4 6
H 9 7 2
G

예제 출력 1

5

위 입력에서 '합'을 이루는 모든 그림 조합은 (1,5,6), (2,3,5), (2,4,6), (2,7,9), (6,8,9) 5가지가 있다.

알고리즘 분류

• 구현

풀이

합으로 묶어주는 과정에서 삼중 for문을 사용했는데, 그림은 9개까지밖에 없기 때문에 경우의 수가 그렇게 많지 않아 시간이 오래 걸리는 작업은 아닐 거라고 생각했기 때문에 삼중 for문을 사용하였다. 나머지는 문제에서 주어진 조건대로 코드를 짜면 되는 어려운 문제는 아니었다.

코드

#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 500
#define INF 1e9

using namespace std;
struct INFO {
	string S, C, B;
};

struct GROUP {
	int A, B, C;
};

int N;
vector<INFO> Picture;
vector<GROUP> HAP;
bool G_Flag = false;
bool visited[MAX];
int answer = 0;

bool All_Same(string X, string Y, string Z) {
	// 세 속성 전부가 모두 같은지를 따진다.
	if ((X == Y) && (Y == Z) && (Z == X)) {
		return true;
	}
	return false;
}

bool All_Not_Same(string X, string Y, string Z) {
	// 세 속성 전부가 모두 다른지를 따진다.
	if ((X != Y) && (Y != Z) && (Z != X)) {
		return true;
	}
	return false;
}

void Picture_Setting() {
	for (int i = 0; i < 9; i++) {
		for (int j = i + 1; j < 9; j++) {
			for (int k = j + 1; k < 9; k++) {
				bool Flag = true;
				// 세 속성 전부가 같거나 전부 다른 경우 true, 아니면 false
				if ((!All_Same(Picture[i].S, Picture[j].S, Picture[k].S)) && (!All_Not_Same(Picture[i].S, Picture[j].S, Picture[k].S))) {
					Flag = false;
				}
				if ((!All_Same(Picture[i].C, Picture[j].C, Picture[k].C)) && (!All_Not_Same(Picture[i].C, Picture[j].C, Picture[k].C))) {
					Flag = false;
				}
				if ((!All_Same(Picture[i].B, Picture[j].B, Picture[k].B)) && (!All_Not_Same(Picture[i].B, Picture[j].B, Picture[k].B))) {
					Flag = false;
				}
				if (Flag) { // 세 속성 전부가 같거나 전부 다른 경우에만 세 그림은 합이 된다.
					HAP.push_back({ i,j,k });
				}
			}
		}
	}
}

bool Find_HAP(int X, int Y, int Z) {
	for (int i = 0; i < HAP.size(); i++) {
		if ((HAP[i].A == X) && (HAP[i].B == Y) && (HAP[i].C == Z) && (!visited[i])) {
			// 이미 찾은 합은 다시 찾으면 안 되기 때문에, 찾았다는 표시를 해준다.
			visited[i] = true;
			return true;
		}
	}
	return false;
}

bool Find_G() {
	for (int i = 0; i < HAP.size(); i++) {
		if (!visited[i]) { // 하나라도 찾지 않은 합이 있다면 false를 return한다.
			return false;
		}
	}
	return true;
}

int main() {
	FIRST
	for (int i = 0; i < 9; i++) {
		string S, C, B;
		cin >> S >> C >> B;
		Picture.push_back({ S,C,B });
	}
	Picture_Setting(); // 우선 9개의 그림을 조건에 맞춰서 합으로 묶어준다.
	cin >> N;
	for (int i = 0; i < N; i++) {
		string A;
		cin >> A;
		if (A == "H") {
			int X, Y, Z;
			cin >> X >> Y >> Z;
			int tmp[3] = { X,Y,Z };
			sort(tmp, tmp + 3);
			bool b = Find_HAP(tmp[0] - 1, tmp[1] - 1, tmp[2] - 1);
			if (b) { // 외친 번호의 그림 세 장이 합이라면 점수+1
				answer += 1;
			}
			else { // 아니라면 점수-1
				answer -= 1;
			}
		}
		else if (A == "G") {
			bool b = Find_G();
			if (b && !G_Flag) { // 합을 다 찾고, 결을 외치면서 3점을 받은 적이 없다면 점수+3
				G_Flag = true;
				answer += 3;
			}
			else { // 그게 아니라면 점수-1
				answer -= 1;
			}
		}
	}
	cout << answer << "\n";

	return 0;
}