[BOJ] 1331. 나이트 투어

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

1331번: 나이트 투어

1. 나이트의 이동 경로가 맞는지
2. 모든 칸을 정확히 한 번씩만 방문했는지
3. 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는지

모든 이동에서 위의 1번과 2번의 경우를 확인해주고 마지막 칸에서 3번 조건을 확인한다.

하나라도 조건에 맞지 않다면 Invalid를 출력하고 모든 조건을 만족한다면 Valid를 출력한다.

 

 

현재 좌표가 x, y 라고 할 때, 나이트가 이동할 수 있는 경로는 위의 그림과 같다.

즉, (x, y)와 이동할 좌표의 차이의 절댓값이

x가 1인 경우에 y는 2이고, x가 2인 경우에 y는 1이면 된다.

 

 

#include <iostream>
#include <string>
#include <cmath>
#define MAX 36
using namespace std;
 
 
bool visit[36][36];
 
bool check(int x, int y, int nx, int ny) {
    int diffx = abs(nx - x);
    int diffy = abs(ny - y);
 
    if (diffx == 1 && diffy == 2) return true;
    else if (diffx == 2 && diffy == 1) return true;
 
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    bool valid = true;
 
    string now, next;
    
    //시작칸 입력
    cin >> now;
 
    int sx, sy;
    int x, y, nx, ny;
 
    //시작칸 좌표
    sx = now[0] - 'A';
    sy = now[1] - '1';
    
    int cnt = 1;
    x = sx;
    y = sy;
    visit[x][y] = true;
 
 
    while (cnt++ < MAX) {
        cin >> next;
        if (!valid) continue;
 
 
        nx = next[0] - 'A';
        ny = next[1] - '1';
 
 
        //방문 확인
        if (visit[nx][ny]) {
            valid = false;
            continue;
        }
 
 
        //방문 표시
        visit[nx][ny] = true;
 
 
        //나이트의 이동경로가 맞는지 검사
        bool flag = check(x, y, nx, ny);
        //나이트의 이동경로로 갈 수 없다면 Invalid
        if (!flag) valid = false;
 
        
        //이동한 좌표를 현재좌표로 바꿔준다.
        now = next;
        x = nx;
        y = ny;
    }
 
 
    //다시 시작칸으로 돌아갈 수 있는지 검사
    if (!check(x,y,sx,sy)) valid = false;
 
 
    if(valid) cout << "Valid" << '\n';
    else cout << "Invalid" << "\n";
 
 
    return 0;
}