[백준 C++] 4921 나무블록

문제

블록은 아래와 같은 나무 조각 8개를 이용해서 하는 게임이다.

이 게임의 목표는 아래와 같은 조건을 지키면서 주어진 나무 조각을 이용해 가장 넓은 직사각형을 만드는 것이다.

1. 가장 왼쪽 조각은 1번 조각, 가장 오른쪽 조각은 2번 조각이어야 한다.
2. 인접한 조각은 서로 맞물려야 한다. 예를 들어, 4번 조각과 5번 조각은 항상 1번 조각의 오른쪽에 있어야 한다. 또, 4번 조각은 1번이나 3번조각의 오른쪽에 있을 수 있다.
3. 1번 조각의 왼쪽과 2번 조각의 오른쪽에 맞물리는 조각은 없다.
4. 각각의 1번 조각에 대해서, 대응하는 2번 조각이 있어야 하고, 5번 조각에 대해서도 대응하는 6번 조각이 있어야 한다.

예를 들어, 아래 2가지는 올바른 배치이다.

하지만, 아래 세 가지는 올바르지 않다.

세희는 이 게임을 앱으로 만들고 있다. 지금 구현할 부분은 사용자가 맞춘 블록이 문제의 조건에 올바른지 아닌지 판별하는 것이다.

한 사용자가 맞춘 블록 게임의 결과가 주어졌을 때, 올바른지 아닌지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 조각은 문제의 그림에 나와있는 숫자로 주어진다. 숫자는 공백없이 주어진다. 적어도 1개의 조각이 주어지며, 조각 10,000개를 넘기는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

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

풀이

항상 큰문제를 작은 단위로 분할하여 해결하도록 생각해본다.
나무블럭만을 놓고보면 고려해야할 가짓수가 많아보이는데 사실 조건을 요약하면

1. 1번, 2번블럭은 각각 제일왼쪽끝, 오른쪽끝에만 와야함
2. 두블럭사이가 맞물려야함

여기서 블럭이맞물림에포인트를두어 모든블럭을 순차적으로 검색, 이전블럭의오른쪽과 현재블럭의 왼쪽을 데이터화하여
올바른 조합인지 확인하면된다.

필자의경우이와같이 데이터화하였다. 사실 우리는 이전블럭의 오른쪽에만 관심이있다.

따라서 블럭번호를통해 블럭의 좌우 상태를 정수로변환시켜주는함수
결과적으로 이전과 현재블럭이 맞물리는부분이 올바른지 확인하는 함수

이렇게 크게 두가지를 구현하면 된다.

아래는 전체코드

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::pair;

int cnt = 0; //몇번째 케이스인가
//블럭의 좌,우상태를 정수로나타낸 값
//[0]:좌 [1]:우
//0: 반듯함(1번,2번과같은)
//1: 볼록사각형
//2: 볼록원형
//3: 오목사각형
//4: 오목원형
int preBlock[2]; //이전블럭
//사실 preBlock의 0번, 좌측은 계산상필요가 없음

void input();
pair<int, int> findBlockKey(char b); //현재나무블럭의 좌우상태 정수로 변환
void setPrevBlock(int left, int right); //이전블럭상태를 설정
bool checkBlock(int left, int right); //이전블럭과 현재블럭이 맞물릴수 있는가 확인


void input() {
	while (true) {
		char in[10001]; //입력받은 블럭조합
		int size = 0; //블럭조각 갯수

		scanf("%s", &in);
		if (in[0] == '0') //종료조건
			break;

		for (int i = 0; i < 10001; i++) { //사용된 블럭갯수 파악
			if (in[i] == '\0')
				break;
			size++; 
		}
		cnt++; //몇번째 블럭인가.
		bool possible = true;

		if (in[0] == '1' && in[size-1] == '2') { //블럭조합의 처음과끝이 1번과 2번이어야 정상
			for (int i = 0; i < size; i++) { //블럭조합의 처음부터 끝까지 탐색
				auto keys = findBlockKey(in[i]); //현재블럭의 좌우 상태를 정수로 변환
				if (i == 0) {//첫회에는 이전블럭 세팅만하고 넘어간다.
					setPrevBlock(keys.first, keys.second);
				}
				else { //첫회이후에는 이전블럭과 현재블럭을 비교하여 가능한지 확인
					//checkBlock: 이전과 현재의 블럭이 맞물릴수있는 상태인지 확인
					if (!checkBlock(keys.first, keys.second)) { //false리턴받을시 불가능함을 출력
						printf("%d. NOT\n", cnt);
						possible = false; //불가능하다.
						break;
					}
				}
			}
		}
		else { //블럭조합의 처음과 끝이 비정상인경우 바로종료
			printf("%d. NOT\n", cnt);
			possible = false;
		}
		//위 과정에서 걸러지지않은경우 가능한 조합임을 출력
		if (possible) {
			printf("%d. VALID\n", cnt);
		}
	}


}

//입력받은 나무블럭번호에따라 블럭의 좌, 우 상태를 정수로 리턴
std::pair<int, int> findBlockKey(char b) {
	int res1, res2;
	switch (b) {
	case '1':
		res1 = 0; //반듯
		res2 = 3; //오목사각형
		break;
	case '2':
		res1 = 3; //오목사각형
		res2 = 0; //반듯
		break;
	case '3':
		res1 = 3; //오목사각
		res2 = 3; //오목사각
		break;
	case '4':
		res1 = 1; //볼록사각
		res2 = 1; //볼록사각
		break;
	case '5':
		res1 = 1; //볼록사각
		res2 = 4; //오목원형
		break;
	case '6':
		res1 = 4; //오목원형
		res2 = 1; //볼록사각
		break;
	case '7':
		res1 = 4; //오목원형
		res2 = 4; //오목원형
		break;
	case '8':
		res1 = 2; //볼록원형
		res2 = 2; //볼록원형
		break;
	}

	return { res1, res2 };
}

//이전블럭을 재설정하는 함수
void setPrevBlock(int left, int right) {
	preBlock[0] = left;
	preBlock[1] = right;
}

//현재블럭의 좌우상태를 정수로 전달받아 이전블럭과비교하여 가능한 조합인지 확인
//true : 정상
//false 를 리턴할시 불가능함을 출력하고 종료
bool checkBlock(int left, int right) { //현재블럭의상태 left, right
	int preBlockRight = preBlock[1]; //이전블럭의 오른쪽부분
	int nowBlockLeft = left; //현재블럭의 왼쪽부분
	
	bool possible = false;
	//두개가 맞물릴수있는 경우면 정상이다.
	if ((preBlockRight == 1 && nowBlockLeft == 3) ||
		(preBlockRight == 3 && nowBlockLeft == 1) || 
		(preBlockRight == 2 && nowBlockLeft == 4) || 
		(preBlockRight == 4 && nowBlockLeft == 2))
		possible = true;

	//이전블럭 을 현재블럭상태로 갱신
	setPrevBlock(left, right);

	return possible;
}

int main(void) {
	input();

	return 0;
}