[BOJ 27495 // C++] 만다라트 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27495번 문제인 만다라트 만들기이다.
문제는 아래 링크를 확인하자.

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

27495번: 만다라트 만들기

각 여덟 중간목표를 문제의 조건에 맞는 알파벳순으로 방문하면서 그 중간목표와 각 중간목표별 세부목표를 문제의 조건에 맞는 알파벳순을 이용해 순서에 맞게 출력하는 것으로 문제를 해결하자.

 

주어진 문자열의 사전순 규칙은 string 자료형의 기본 크기비교 연산자의 정의와 동일하므로 string을 이용해 구현하면 문제를 구현을 편리하게 할 수 있다. 글쓴이는 priority queue 자료구조를 이용해 문제를 해결하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

string s[9][9];

priority_queue<pair<string, pair<int, int>>, vector<pair<string, pair<int, int>>>, greater<>> pqA;
priority_queue<string, vector<string>, greater<>> pqB;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int r = 0; r < 9; r++) {
		for (int c = 0; c < 9; c++) {
			cin >> s[r][c];
		}
	}

	pqA.push(make_pair(s[1][1], make_pair(1, 1)));
	pqA.push(make_pair(s[1][4], make_pair(1, 4)));
	pqA.push(make_pair(s[1][7], make_pair(1, 7)));
	pqA.push(make_pair(s[4][1], make_pair(4, 1)));
	pqA.push(make_pair(s[4][7], make_pair(4, 7)));
	pqA.push(make_pair(s[7][1], make_pair(7, 1)));
	pqA.push(make_pair(s[7][4], make_pair(7, 4)));
	pqA.push(make_pair(s[7][7], make_pair(7, 7)));

	for (int i = 1; i < 9; i++) {
		string cur = pqA.top().first; int r = pqA.top().second.first, c = pqA.top().second.second; pqA.pop();
		cout << '#' << i << ". " << cur << '\n';

		pqB.push(s[r - 1][c - 1]);
		pqB.push(s[r - 1][c]);
		pqB.push(s[r - 1][c + 1]);
		pqB.push(s[r][c + 1]);
		pqB.push(s[r + 1][c + 1]);
		pqB.push(s[r + 1][c]);
		pqB.push(s[r + 1][c - 1]);
		pqB.push(s[r][c - 1]);

		for (int j = 1; j < 9; j++) {
			cout << '#' << i << '-' << j << ". " << pqB.top() << '\n';
			pqB.pop();
		}
	}
}