1215. [S/W 문제해결 기본] 3일차 - 회문1 D3

"기러기", "토마토", "스위스"와 같이 똑바로 읽어도 거꾸로 읽어도 똑같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.

8x8 평면 글자판에서 제시된 길이를 가진 회문의 개수를 구하라.
 

위와 같은 글자판이 주어졌을 때, 길이가 5인 회문은 붉은색 테두리로 표시된 4개이므로 4를 반환하면 된다.


[제약 사항]

각 칸의 들어가는 글자는 'A', 'B', 'C' 중 하나이다.

ABA도 회문이며, ABBA도 회문이다. A 또한 길이 1짜리 회문이다.

가로 또는 세로로 이어진 회문의 개수만 센다.

아래 그림에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.

 

[입력]

총 10개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 찾아야 하는 회문의 길이가 주어지며, 다음 줄에 8x8 크기의 글자판이 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 개수를 출력한다.

입력4
CBBCBAAB
CCCBABCB
CAAAACAB
BACCCCAC
AABCBBAC
ACAACABC
BCCBAABC
ABBBCCAA
4
BCBBCACA
BCAAACAC
ABACBCCB
AACBCBCA
ACACBAAA
ACCACCCB
AACAAABA
CACCABCB
...

 

출력#1 12
#2 10

 

• 풀이

 

8*8 배열에서 가로, 세로 방향으로 n개의 길이만큼의 문자열을 찾고, 찾은건 reverse 해서 원본과 같은지 비교하는 방식으로 풀었다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>

using namespace std;

int main() {

	for (int t = 1; t <= 10; t++) {
		int res = 0, n; cin >> n;
		vector<vector<char>> arr(8, vector<char>(8));

		for (int i = 0; i < 8; i++) {
			string s; cin >> s;
			for (int j = 0; j < 8; j++) arr[i][j] = s[j];
		}

		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {

				// 가로 문자열 가져오기
				if (8 - j >= n) {
					string tmp = "";
					for (int k = 0; k < n; k++) tmp += arr[i][j + k];
					string tmp2 = tmp;
					reverse(tmp.begin(), tmp.end());
					if (tmp == tmp2) res++;
				}

				// 세로 문자열 가져오기
				if (8 - j >= n) {
					string tmp = "";
					for (int k = 0; k < n; k++) tmp += arr[j + k][i];
					string tmp2 = tmp;
					reverse(tmp.begin(), tmp.end());
					if (tmp == tmp2) res++;
				}
			}
		}
		cout << "#" << t << " " << res  << '\n';
	}
	return 0;
}