[백준] 1331 나이트 투어 (C++)

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

1331번: 나이트 투어

문제

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

영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.

입력

36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

풀이

방문한 위치를 char로 이루어진 배열로 받아 x값과 y값을 구한다.

이후 매번 이전 x, y값과 현재의 x, y값을 비교하여 나이트에 맞게 움직이는 지 확인하고,

현재의 x,y값을 6*6으로 이루어진 좌표상에 기록하여 이전에 방문하였던 장소인지 확인한다.

마지막으로 마지막 위치에서 현재 위치로 이동 가능한지 여부를 확인하면 끝이다.

 

* 위치를 입력받을 때 char knight[2]로 할 경우 특정 좌표가 계속 이상하게 설정되어 삽질을 오래 했다...

코드

#include <iostream>
#include <string>
using namespace std;
bool isKnight(int a, int b, int c, int d){ // 나이트에 맞게 이동하는지 확인
    if ((abs(a-c)+abs(b-d) == 3) && (abs(a-c)*abs(b-d) == 2)){ //합이 3이고 곱이 2인 경우
        return true;
    }
    return false;
}

int main(){
    string answer = "Valid";
    int x, y, startX, startY, prevX, prevY;
    int coordinate[6][6] = {}; // 6 * 6의 좌표를 0으로 초기화

    for (int i = 0; i < 36; i++){
        char knight[3]; // knight[2]로 설정하면 A1의 값이 계속 이상하게 설정되어 knight[3]으로 했습니다...
        cin >> knight;

        x = knight[0] - 'A';
        y = knight[1] - '1';

        if (coordinate[x][y] == 1){ // 이전에 나왔던 좌표값이 다시 나온 경우
            answer = "Invalid";
        }

        if (i){ // i가 0이 아닐 때
            if (!isKnight(x, y, prevX, prevY)){ // 나이트에 맞게 이동하지 않는 경우
                answer = "Invalid";
            }
        }
        else{ // i가 1일 때
            startX = x;
            startY = y;
        }

        if (i == 35){ // i가 35일 때
            if (!isKnight(x, y, startX, startY)){ // 마지막 좌표에서 처음 좌표로 이동할 수 없는 경우
                answer = "Invalid";
            }
        }

        coordinate[x][y] = 1; // 방문한 좌표는 1로 입력
        prevX = x; // 현 위치의 x좌표 저장
        prevY = y; // 현 위치의 y좌표 저장
    }

    cout << answer;
}