백준 1331 나이트 투어 (c++) : 피너클

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

1331번: 나이트 투어

구현문제다.

bool visited[7][7];
int dx[8] = { 2, 2, 1, -1, -2, -2, -1, 1 };
int dy[8] = { -1, 1, 2, 2, 1, -1, -2, -2 };

visited는 나이트가 이동한 장소

dx와 dy는 나이트가 이동하는 위치를 나타낸다.

string s;
cin >> s;
int x = s[0] - 'A';
int y = s[1] - '1';
int firstx = x, firsty = y;
visited[x][y] = true;
bool chk = true;

s는 입력받을 문자열

x는 A, B, C, D, E, F 중에서 하나

y는 1, 2, 3, 4, 5, 6 중에서 하나를 나타낸다.

firstx와 firsty는 마지막에 돌아와야하니 저장해둔다.

visited에 방문을 표시하고 앞으로 모든 조건을 확인할 bool chk를 선언한다.

for (int i = 1; i < 36; i++) {
	cin >> s;
	int nextx = s[0] - 'A';
	int nexty = s[1] - '1';

35번동안 반복하며 s를 입력받은 다음

nextx와 nexty에 위치를 입력한다.

bool is = false;
for (int j = 0; j < 8; j++) {
	if (x + dx[j] == nextx && y + dy[j] == nexty) {
		is = true;
		break;
	}
}

is는 나이트가 현재위치 (x, y)에서 다음위치 (nextx, nexty)로 이동할수 있는지 확인하는 bool형이다.

dx와 dy를 이용해 이동할수 있는지 확인하고 이동할수 있는경우 is를 true로 설정한뒤 반복문을 빠져나온다.

	if (is) {
		x = nextx;
		y = nexty;
		visited[x][y] = true;
	}
	else {
		chk = false;
		break;
	}
}

만약 is가 true라면 x에 nextx를, y에 nexty를 넣고 visited에 방문을 표시한다.

만약 아니라면 chk를 false로 바꾼뒤 반복문을 빠져나온다.

if (!chk) {
	cout << "Invalid" << endl;
}

만약 chk가 false라면 Invalid를 출력한다.

else {
	chk = false;
	for (int i = 0; i < 8; i++) {
		if (x + dx[i] == firstx && y + dy[i] == firsty) {
			chk = true;
		}
	}
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			if (!visited[i][j]) {
				chk = false;
			}
		}
	}
	if(!chk) cout << "Invalid" << endl;
	else cout << "Valid" << endl;
}

true라면 현재 위치 (x, y)에서 처음위치 (firstx, firsty)로 이동할수 있는지 확인하고

모든 위치를 방문했는지 확인한다.

만약 chk가 위의 조건을 만족하지 못해 false로 바뀌었다면 Invalid를 출력하고 아니면 valid를 출력한다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool visited[7][7];
int dx[8] = { 2, 2, 1, -1, -2, -2, -1, 1 };
int dy[8] = { -1, 1, 2, 2, 1, -1, -2, -2 };

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	string s;
	cin >> s;
	int x = s[0] - 'A';
	int y = s[1] - '1';
	int firstx = x, firsty = y;
	visited[x][y] = true;
	bool chk = true;

	for (int i = 1; i < 36; i++) {
		cin >> s;
		int nextx = s[0] - 'A';
		int nexty = s[1] - '1';

		bool is = false;
		for (int j = 0; j < 8; j++) {
			if (x + dx[j] == nextx && y + dy[j] == nexty) {
				is = true;
				break;
			}
		}
		if (is) {
			x = nextx;
			y = nexty;
			visited[x][y] = true;
		}
		else {
			chk = false;
			break;
		}
	}
	if (!chk) {
		cout << "Invalid" << endl;
	}
	else {
		chk = false;
		for (int i = 0; i < 8; i++) {
			if (x + dx[i] == firstx && y + dy[i] == firsty) {
				chk = true;
			}
		}
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 6; j++) {
				if (!visited[i][j]) {
					chk = false;
				}
			}
		}
		if(!chk) cout << "Invalid" << endl;
		else cout << "Valid" << endl;
	}
}

전체코드다.