BaekJoon 1331번: 나이트 투어(C++)

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

1331번: 나이트 투어

풀이법

1) 배열 자체가 크지 않은 배열이기에, 시간 초과의 걱정 없이 세밀하게 구현을 잘 해낼 수 있는지를 묻는 문제라고 생각한다.

2) 모든 칸을 정확히 한 번만 방문해야 하기에 visited배열을 통해서 방문 여부를 확인했고, 마지막 방문 칸에서 다시 시작점으로 돌아와야 하기에, 시작점은 visited배열에 처음에 넣지 않았다.

3) 나이트가 갈 수 없는 칸일 경우, 바로 Invaild를 써서 return 시켜주었고, 마지막에는 visited배열을 모두 확인함으로써 모든 칸에 방문했는지 확인 후 Vaild 값을 주었다. 

4) 미리 나이트가 갈 수 있는 8개의 칸을 담아둔 배열을 통해 반복 시키는 것이 오타를 막는 좋은 방법이기에 앞으로도 계속 활용할 예정이다.

int vx[8] = { -2,-2,-1,1,2,2,1,-1 };
int vy[8] = { -1,1,2,2,1,-1,-2,-2 };

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#define INF 987654321
using namespace std;

int n;
int arr[7][7];
bool visited[7][7];
int vx[8] = { -2,-2,-1,1,2,2,1,-1 };
int vy[8] = { -1,1,2,2,1,-1,-2,-2 };

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int nowX = (int)(6 - (s[1] - '0'));
	int nowY = (int)(s[0] - 'A');
	int startX = nowX;
	int startY = nowY;
	for (int i = 1; i <= 35; i++)
	{
		string s;
		cin >> s;
		int nextX = (int)(6 - (s[1] - '0'));
		int nextY = (int)(s[0] - 'A');
		bool check = false;
		for (int j = 0; j < 8; j++)
		{
			int valX = nowX + vx[j];
			int valY = nowY + vy[j];
			if (valX < 0 || valY < 0 || valX >= 6 || valY >= 6)
				continue;
			if (valX == nextX && valY == nextY&&!visited[valX][valY])
			{
				check = true;
				nowX = nextX;
				nowY = nextY;
				visited[valX][valY] = true;
				break;
			}
		}
		if (check == false)
		{
			cout << "Invalid";
			return 0;
		}
	}
	bool check = false;
	for (int j = 0; j < 8; j++)
	{
		int valX = nowX + vx[j];
		int valY = nowY + vy[j];
		if (valX < 0 || valY < 0 || valX >= 6 || valY >= 6)
			continue;
		if (valX == startX && valY == startY && !visited[valX][valY])
		{
			check = true;
			visited[valX][valY] = true;
			break;
		}
	}
	if (check == false)
	{
		cout << "Invalid";
		return 0;
	}
	for (int i = 0; i < 6; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			if (visited[i][j] == false)
			{
				cout << "Invalid";
				return 0;
			}
		}
	}
	cout << "Valid";
}