나이트 투어

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0710 ~ 0750
bool vis[7][7];
vector<string> sv;
int dr[8] = {-2, -2, 2, 2, -1, -1, 1, 1};
int dc[8] = {-1, 1, -1, 1, -2, 2, -2, 2};
int charToInt(char c)
{
    if(c == 'A') return 1;
    if(c == 'B') return 2;
    if(c == 'C') return 3;
    if(c == 'D') return 4;
    if(c == 'E') return 5;
    return 6;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0;i<36;i++)
    {
        string s;
        cin >> s;
        sv.push_back(s);
    }
    sv.push_back(sv[0]); // 마지막 종료좌표에서 시작좌표로 갈 수 있는지 검사하기 위함
    /* 시작 좌표 설정
       --> 마지막에 돌아와야 하니까 vis처리 X */
    pair<int,int> pre={0,0};
    int r = 7-(sv[0][1]-'0');
    int c = charToInt(sv[0][0]);
    pre = {r,c};
    for(int i=1;i<sv.size();i++) 
    {
        string ss = sv[i];
        int r = 7-(ss[1]-'0');
        int c = charToInt(ss[0]);
        // 나이트가 이동 가능한 범위인지 검사 & 이미 방문한 점이면 실패
        bool flag = false;
        for(int dir=0;dir<8;dir++)
        {
            int nr = pre.first + dr[dir];
            int nc = pre.second + dc[dir];
            if(nr<1 or nc<1 or nr>6 or nc>6) continue;
            if(nr == r and nc == c) {
                flag = true;
                break;
            }
        }
        if(flag == false or vis[r][c]) {
            cout << "Invalid";
            return 0;
        }
        vis[r][c] = true;
        pre = {r, c};
    }
    cout << "Valid";
    return 0;
}

• 핵심
  : 마지막 좌표에서 처음으로 오는 것도 검사해야 하니까 sv[0] 더한 뒤 검사해야 함