[BOJ] 백준 1331 나이트 투어

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

 Input 

A1

B3

A5

C6

E5

F3

D2

F1

E3

F5

D4

B5

A3

B1

C3

A2

C1

E2

F4

E6

C5

A6

B4

D5

F6

E4

D6

C4

B6

A4

B2

D1

F2

D3

E1

C2

 

 Output 

Valid

6 x 6 체스판에서 나이트가 이동하므로 나이트 투어를 위해서는

처음 지점을 포함해서 총 36개 칸을 지나쳐야 합니다.

먼저, 주어진 경로대로 나이트가 이동할 수 있는지 확인합니다.

나이트가 한번에 이동할 수 있는 지점은 아래와 같습니다.

 

주어진 입력은 모든 칸을 순서없이 나열한 것이므로 이동 가능 여부만 확인하며,

별도 모든 칸을 투어했는지는 확인할 필요가 없습니다.

그리고, 마지막 지점에서 다시 처음지점으로 돌아와서 나이트 투어를 끝낼 수 있는지 확인합니다.

 

---

#include <iostream>
#include <string>
using namespace std;
 
bool isValid, visited[6][6];
int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };
int startX, startY, curX, curY, nextX, nextY, toX, toY;
int main() {
    string str; cin >> str;
    startX = 5 - (str[1] - '1');
    startY = str[0] - 'A';
    curX = startX;
    curY = startY;
    visited[curX][curY] = true;
 
    for (int i = 1; i < 36; i++) {
        cin >> str;
        toX = 5 - (str[1] - '1');
        toY = str[0] - 'A';
        
        isValid = false;
        for (int j = 0; j < 8; j++){
            nextX = curX + dx[j];
            nextY = curY + dy[j];
            if (nextX < 0 || nextX >= 6 || nextY < 0 || nextY >= 6) 
                continue;
            // 가능한 이동 지점 중 입력받은 지점이 존재하는 경우(재방문 x)
            if (nextX == toX && nextY == toY && !visited[nextX][nextY]) {
                visited[nextX][nextY] = true;
                curX = nextX;
                curY = nextY;
                isValid = true;
                break;
            }
        }
        if (!isValid) {
            printf("Invalid");
            return 0;
        }
    }
 
    // 모든 지점을 투어하고 난 뒤, 처음 지점으로 올 수 있는지 확인
    for (int i = 0; i < 8; i++){
        nextX = curX + dx[i];
        nextY = curY + dy[i];
        if (nextX < 0 || nextX >= 6 || nextY < 0 || nextY >= 6)
            continue;
 
        if (nextX == startX && nextY == startY) {
            printf("Valid");
            return 0;
        }
    }
 
    printf("Invalid");
}