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

나이트 투어

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

6836

2066

1755

31.696%

문제

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

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

입력

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

출력

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

---

문제풀이

나이트의 이동경로는 총 8가지이다.

이 하나하나의 경우의 수를 조건문으로 넣자니 맘에들지 않았다.

고민고민해보니 이동한 곳 - 원래 있던 곳의 값을 계산해보면, (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)

다음과 같이 8가지 경우의 수가 나온다.

앞의 것을 x, 뒤에 것을 y로 한뒤 절댓값을 씌우면 결국 x가 1일때 y는 2가 되어야 하고, x가 2일때 y는 1이어야 한다.

이 방법을 적용하여 올바른 위치로 이동했는지 확인했다.

 

문제를 제대로 안읽어 추가 조건들을 빼먹었다.

 

같은곳을 방문하는경우

올바른 위치로 이동했더라도 같은 위치로 이동했을 수 있다.

 

마지막 이동이후 처음 위치로 이동 가능한지

36곳 모두 한번씩 들렸다고 하더라도 맨 마지막 위치에서 맨 처음 위치로 이동이 불가능한 경우가 존재한다.

 

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int visited[6][6];

int main() {
    string before;
    cin >> before;
    visited[before[0]-'A'][before[1]-'1'] = 1;
    string start = before;
    for(int i=1; i<36; i++) {
        string s;
        cin >> s;
        int a = abs(before[0] - s[0]);
        int b = abs(before[1] - s[1]);
        // 올바른 위치로 이동했는지, 중복이동이 없는지 확인
        if(!((a == 1 && b == 2) || (a == 2 && b == 1)) || visited[s[0]-'A'][s[1]-'1']) {
            cout << "Invalid";
            return 0;
        }
        visited[s[0]-'A'][s[1]-'1'] = 1;
        before = s;
    }
    // 처음 위치로 이동가능한지 확인
    int a = abs(start[0] - before[0]);
    int b = abs(start[1] - before[1]);
    if(!((a == 1 && b == 2) || (a == 2 && b == 1))) {
        cout << "Invalid";
        return 0;
    }
    cout << "Valid";
    return 0;
}