1331번

1331번 - 나이트 투어

시뮬레이션 문제.

주어진 순서대로 나이트가 움직여야 하기 때문에, 입력을 받으면서 map 변수에 0번부터 35번까지 순서를 입력해주었다.

그 후에 0~35번까지 for문을 돌면서 , 각 각의 나이트가 움직일 수 있는 8가지 방향을 체크했다. 

시작점인 0번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 1번 칸이 존재하면 움직인다.

1번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 2번 칸이 존재하면 움직이다.

. . . 

마지막 35번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 0번째 시작점이 존재하면 움직인다.

이런식으로 문제를 풀어나가면서 만약 탐색해서 다음 칸을 찾지 못하면 INVALID 가 된다.

하지만 마지막까지 다 탐색할 수 있다면 VALID 가 되므로 답을 출력한다.

<정답 코드>

#include<iostream>
#include<string>
 
#define SIZE 36
using namespace std;
 
int dx[8] = { 1,-1,1,-1,2,-2,2,-2 };
int dy[8] = { 2,2,-2,-2,1,1,-1,-1 };
int map[6][6];
string str[36];
int main()
{
    //freopen("input.txt", "r", stdin);
    int sx, sy, x, y;
    for (int i = 0; i < SIZE; i++)
    {
        cin >> str[i];
        x = str[i][0] - 'A';
        y = str[i][1] - '1';
        //움직이는 순서 map 변수에 저장
        map[x][y] = i;
        
        //시작위치 sx,sy 보관
        if (i == 0)
        {
            sx = x;
            sy = y;
        }
    }
 
    x = sx, y = sy;
 
    bool ans = true;
    for (int i = 0; i < SIZE; i++) 
    {
        bool chk = false;
        //나이트가 움직이는 8가지 방법
        for (int d = 0; d < 8; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && ny >= 0 && nx < 6 && ny < 6)
            {
                //나이트가 움직였을 때 나오는 칸이 다음 순서의 칸 일 경우
                if (i != SIZE-1 && map[nx][ny] == i + 1)
                {
                    x = nx, y = ny;
                    chk = true;
                    break;
                }
 
                //맨마지막 칸에서 움직였을 때 시작점이 나오는 경우
                if (i == SIZE-1 && map[nx][ny] == 0)
                {
                    x = nx, y = ny;
                    chk = true;
                    break;
                }
            }
        }
 
        if (!chk) {
            ans = false;
            break;
        }
    }
 
    if (ans)
        cout << "Valid" << endl;
    else
        cout << "Invalid" << endl;
 
 
 
 
    return 0;
}