(C++) - 백준(BOJ) 1331 : 나이트 투어

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

1331번: 나이트 투어

구현 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

방향을 결정할 일차원 배열 dx, dy, 중간경로가 valid한지 결정할 ans, 위치와 시작 점을 저장할 curX, curY, oriX, oriY와 방문여부 visited를 선언해줍니다.

📔 풀이과정

1. 시작점을 입력받고 첫 좌표를 curX, curY에 저장해줍니다.

 

2. 그리고 시작점으로 다시 돌아왔는지 판별하기 위한 변수 oriX, oriY에 curX, curY를 저장해줍니다.

 

3. 이후 35개의 좌표를 for loop를 수행하며 입력받습니다.

  3-1. 입력받은 후 중간경로가 유효한지 검사하는 canGo함수를 수행합니다. curX, curY에서 x, y로 갈 수 있는지 판별하게 됩니다.   

  3-2. curX, curY좌표를 입력받은 좌표로 갱신해주고 해당 좌표를 방문했으므로 visited[curX][curY] = 1처리해줍니다.

 

4. 마지막으로 다시 돌아와야하므로 canGo함수를 수행하며 유효한지 판별합니다.

📔 정답출력

형태에 맞게 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int dx[8] = {1,2,2,1,-1,-2,-2,-1};
int dy[8] = {2,1,-1,-2,-2,-1,1,2};
bool ans = true;
int curX, curY, oriX, oriY, visited[6][6];
string s;
vector <string> v;

bool canGo(int curx, int cury, int x, int y){
    int can = 0;
    for(int i = 0; i < 8; i++){
        int nx = curx + dx[i];
        int ny = cury + dy[i];
        if(nx < 0 || nx > 5 || ny < 0 || ny > 5)continue;
        if(nx == x && ny == y) return true;
    }
    return false;
}

bool isAllVisited(){
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++){
            if(!visited[i][j]) return false;
        }
    }
    return true;
}

int main(){
    v.resize(36);
    cin >> s;
    curX = s[0] - 'A';
    curY = s[1] - '1';
    oriX = curX;
    oriY = curY;
    visited[oriX][oriY] = 1;
    for(int i = 1; i < 36; i++){
        cin >> s;
        int x, y;
        x = s[0] - 'A';
        y = s[1] - '1';
        if(!canGo(curX, curY, x, y)) ans = false;
        curX = x;
        curY = y;
        visited[curX][curY] = 1;
    }
    if(ans) {
        if(canGo(curX, curY, oriX, oriY) && isAllVisited()) cout << "Valid";
        else cout << "Invalid";
    }
    else cout << "Invalid";
}