[SW Expert] #1215 S/W 문제해결 기본 3일차 - 회문1

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

dfs를 활용하여 정해진 회문의 횟수만큼 방문했을 시 회문값에 일치하면 result개수를 늘리는 방법으로 해결하였다.

---

2. 코드

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

int line = 0;
char ary[8][8];
char buf[10] = {};
int result = 0;
int dx[4] = {-1 , 1 ,0 , 0};
int dy[4] = {0, 0, -1, 1};
void check(int x, int y, int dept, int val) {
    buf[dept] = ary[x][y];
	if (dept == line-1) {
		string temp;
		string temp2;
		for (int i = 0; i < line; i++) {
			temp = temp + buf[i];
		}
		for (int i = line-1; i >= 0; i--) {
			temp2 = temp2 + buf[i];
		}
		if (temp.compare(temp2) == 0) result++;
	}
	else {
		int nx = x + dx[val];
		int ny = y + dy[val];

		if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8)  return;
		else {
			check(nx, ny, dept + 1, val);
		}
	}
}

int main()
{
	for (int k = 1; k <= 10; k++) {
		cin >> line;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				cin >> ary[i][j];
			}
		}
		result = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				for (int k = 0; k < 4; k++) {
					check(i, j, 0, k);
				}
			}
		}


		cout << "#" << k << " " << result / 2 << endl;
	}
	

}

---

3. 주의사항

dfs를 반복하면서 1번부터 4번까지 1,2,3,4 와 4번부터 1번까지 4,3,2,1을 두번 체크하기 때문에 결과값을 2로 나눠주면 올바른 결과 값이 나온다