[백준,c++] 1331번 - 나이트 투어

문제

1331번: 나이트 투어

 

코드

#include <iostream>
using namespace std;


int map[6][6];
int visited[6][6];

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


char check_alpha(char c){
    if(c=='A') return 0;
    if(c=='B') return 1;
    if(c=='C') return 2;
    if(c=='D') return 3;
    if(c=='E') return 4;
    if(c=='F') return 5;
    return 0;
}

int check_num(int i){
    if(i==6) return 0;
    if(i==5) return 1;
    if(i==4) return 2;
    if(i==3) return 3;
    if(i==2) return 4;
    if(i==1) return 5;
    return 0;
}

bool valid(int before_y, int before_x, int now_y, int now_x){
    for(int i=0; i<8; i++){
        int ny = before_y + dy[i];
        int nx = before_x + dx[i];
        if(nx==now_x && ny==now_y) return true;
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int start_y, start_x;
    for(int i=0; i<36; i++){
        string inp; cin>>inp;
        
        int before_y, before_x;
        char c = inp[0];
        int y = check_num(inp[1]-'0');
        int x = check_alpha(c);
        
        if(i==0){
            before_y = y;
            before_x = x;
            start_y = y;
            start_x = x;
            continue;
        }
        
        if(i==35){
            if(visited[y][x]||!valid(start_y, start_x, y,x)){
                cout<<"Invalid";
                return 0;
            }
        }
        
        if(!visited[y][x]){
            if(valid(before_y, before_x, y,x)){
                visited[y][x] = 1;
                before_y = y;
                before_x = x;
            }
            else{
                cout<<"Invalid";
                return 0;
            }
        }
        else{
            cout<<"Invalid";
            return 0;
        }
    }
    cout<<"Valid";

 

풀이

"나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다."

차근차근 문제의 조건에 따라가면서 구현하면 되는 문제입니다. 먼저 체스 말의 입력 위치가 2차원 배열의 어느 좌표인지 계산하였고, 현재 놓을 위치가 이전에 놓은 위치에서 이동할 수 있는 곳인지를 valid함수를 통해서 판별했습니다. 또한 정확히 모든 칸을 한 번씩만 방문해야 하기 때문에 visited 배열을 통해 방문 처리를 하였고, 마지막으로 방문하는 지점일 경우 제일 처음 지점과 비교하여 valid함수에서 판별했습니다.