취미로 코딩하기

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

이번에 볼 문제는 백준 2784번 문제인 가로 세로 퍼즐이다.
문제는 아래 링크를 확인하자.

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

주어진 6개 단어를 모두 사용하여 가로 세로 퍼즐을 올바르게 채울 수 있는지 여부를 판단하는 문제이다.

글쓴이는 주어진 단어들의 각각의 순열에 대하여 첫 세 단어를 가로로 나열한 퍼즐과 나중 세 단어를 세로로 나열한 퍼즐을 만들어 둘이 같은 경우 중 사전순으로 가장 빠른 답안을 출력해 문제를 해결하였다.

모든 순열에 접근하는 것은 next_permutation을 이용해 간단하게 해낼 수 있다.

c++의 문자열은 사전순 비교 연산 '<'가 정의되어 있으므로 사전순 비교 또한 간단하게 구현할 수 있다.

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int pmt[6] = { 0,1,2,3,4,5 };
string s[6];
char bd1[3][3], bd2[3][3];

string ans = "zzzzzzzzzzzz";

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

	for (int i = 0; i < 6; i++) cin >> s[i];

	while (1) {
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) bd1[r][c] = s[pmt[r]][c];
		}

		for (int c = 0; c < 3; c++) {
			for (int r = 0; r < 3; r++) bd2[r][c] = s[pmt[c + 3]][r];
		}

		bool sgn = 1;
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				if (bd1[r][c] != bd2[r][c]) sgn = 0;
			}
		}

		if (sgn) ans = min(ans, s[pmt[0]] + s[pmt[1]] + s[pmt[2]]);

		if (!next_permutation(pmt, pmt + 6)) break;
	}

	if (ans.length() > 9) cout << 0;
	else cout << ans.substr(0, 3) << '\n' << ans.substr(3, 3) << '\n' << ans.substr(6, 3);
}