[BaekJoon/백준] 1331번 나이트 투어

 

나는 문제에서 요하는 대로, 정석적이게 풀어서

다른 분들의 코드보다 다소 복잡할 것 같다고 생각했는데

 

내 코드가 잘 짠 코드인 것 같다..!

 

그리고 이 문제에 도움이 필요한 분들도 풀이가 잘 이해가 되실 수 있을 것 같다.

 

 

체크포인트는 두 가지.

 

1. 경로가 겹치는가
2. 각 경로가 닿을 수 있는 거리인가
   ( 두 경로 A3 B1가 있을 때, (|A - B| == 1 && |3 - 2| == 2) 또는 (|A - B| == 2 && |3 - 1|) == 1 여야 닿을 수 있다)
   

 

체크포인트 1은, 단순히 입력 안에 겹치는 문자가 있을 때로 발견할 수 있다.

차례로 입력을 받으면서 하나의 문자열로 계속 합쳐서 붙여나가고, 이 내에서 중복된 입력이 있으면 해당된다.

 

체크포인트 2는, 이렇게 하나의 문자열로 만든 곳을 분할해서 각 경로가 닿을 수 있는지 확인한다.

빨간색은 문자들의 인덱스를 나타낸다.

초록색 괄호 부분은, 처음 비교하는 박스로 보면 된다.

A1과 B3를 비교하기 때문이다. 그리고 이 반복은 박스를 두칸씩 오른쪽으로 옮기면서 진행한다.

 

가장 마지막 위치 C2와 A1까지 비교해주어야 하기 때문에,  인덱스가 70일때까지 진행하며, 72부터는 범위를 벗어나니까 % 72를 처음부터 해줘서 사이클 배열로 작동하게끔 한다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

    string PATH, str;
    
    
    bool VALID = true;
    
    int REPEAT = 36;
    
    while(REPEAT--) {
        
        cin >> str;
        
        // 체크포인트 1
        if(PATH.find(str) != -1)
            VALID = false;
        
        PATH += str;
        
    }
    
    
    // 체크포인트 2
    for(int i = 0; i <= 70; i+=2 ) {
        
        int gap1 = abs(PATH[i] - PATH[(i + 2) % 72]);
        int gap2 = abs(PATH[i + 1] - PATH[(i + 3) % 72]);
        
        
        if(!((gap1 == 1 && gap2 == 2) || (gap1 == 2 && gap2 == 1))) {
            VALID = false;
            break;
        }
    }
    
    
    cout << ((VALID) ? "Valid" : "Invalid") << "\n";
}

 

 

소요 시간 : 20분