😺 범위를 벗어날 경우 반대방향으로 이동하는 알고리즘 😺

알고리즘을 풀면서 기억해두면 좋을만한 코드를 기록한다. 

 

😺 상황 설명 

고양이가 상하좌우로 L만큼 이동할 때 범위 밖으로 이동한다면 이동방향을 반대로 바꾼 후 이동을 계속 진행한다. 

만약 L의 값이 10억일 때 for문을 10억 번 돌려 고양이가 이동하게 되는 위치를 정하는 것은 비효율적이며 시간초과가 발생한다. 

고양이의 위치를 반복문이 아닌 식을 이용해서 구해보자. 

 

 

 

 

 

🕹️ 구현 방법 

🔹 오른쪽으로 이동할 때 

4x6의 판에서 현재 고양이는 (2, 2)에 위치해 있다.

고양이가 만약 3칸 이동하면 범위에 벗어나지 않는다. 

하지만 오른쪽으로 7칸 이동할 때 범위를 벗어나게 된다.

다음 이동하려는 칸이 범위에 벗어난다면 방향을 반대로 바꿔 이동하고, 최종적으로 (2, 1)에 위치하게 된다. 

12칸 이동하면 동일한 방법으로 (2, 4)에 위치하게 된다 .

 

규칙을 찾아보면, 고양이는

오른쪽으로 이동 ➔ ( (2,  6)은 범위를 벗어남 👉 방향 전환) ➔ 왼쪽으로 이동 ➔ ( (2, -1)은 범위를 벗어남 👉 방향 전환) ➔ 오른쪽으로 이동 👉 다시 제자리 

이런 사이클을 반복하게 된다. 

 

위와 같이 하나의 사이클은 2*(6-1)=10만큼 이동해서 제자리에 돌아오며 일반항으로 2*(M-1) (M은 가로 길이)로 작성할 수 있다. 

그러므로 하나의 사이클의 이동 수보다 훨씬 더 많이(d만큼) 이동하게 된다면 고양이의 위치는 나머지 연산자를 활용해 d%(2*(M-1))로 나타낼 수 있다. 

위에서 12칸만큼 이동한 것을 예로 들어보면, 12%(2*(M-1)) = 2 의 계산 결과가 나오므로 고양이는 2칸 이동하게 되어 (2, 4)에 위치한다. 

---

코드로 작성해보자. 

N x M의 칸에서 현재 고양이의 위치는 (x, y)이며 d칸만큼 오른쪽으로 이동할 것이다. 

현재 위치 기준으로 오른쪽에 남은 칸의 개수는 M-y-1개이다. 

고양이는 현재 위치에서 int dist = d%(2*(M-1))만큼 이동할 것이다. 

만약 오른쪽에 남은 칸의 개수가 dist보다 작다면 👉 (M-y-1)<dist

범위를 넘어가게 되므로 if문을 활용해 반대방향으로 이동한 위치를 구한다.

남은 칸의 개수가 dist보다 크다면 현재 고양이의 위치에서 dist만큼 더해주면 된다. 👉 y+=dist

 

위의 그림에서 4칸 오른쪽으로 이동하면 3칸은 이동하다가 마지막 1칸은 반대방향으로 바꿔 이동하기 때문에 dist-=(M-y-1) 만큼 반대방향으로 이동하는 것으로 계산하면 된다. 계산된 dist는 범위를 벗어나지 않으므로 고양이의 위치는 y=(M-1-dist)가 된다. 

 

그러나 dist가 왼쪽으로 이동하면서 또 범위를 벗어날 수 있다.

예를 들어, 29칸 이동하면 현재 위치에서 29%(2*(6-1)) = 9칸만큼 이동하고 dist-=(M-y-1) 계산 결과, 6칸 만큼 반대방향으로 이동한다. 하지만 왼쪽으로 6칸 이동하면 범위를 벗어나게 된다. 👉 (M-1 < dist)

이럴 경우에는 dist-= (M-1)로 계산하여 고양이는 y=dist 위치로 이동하게 된다. 

// 오른쪽 이동 
public static Node moveRight(int x, int y, int d) {
    int dist = d%(2*(M-1));
    //현재 위치 기준 오른쪽에 남은 칸 = M-y-1
    if(M-y-1<dist) {
        dist-=M-y-1;
        if(M-1<dist) {
            dist-=M-1;
            y = dist;
        }else y = M-1-dist;
    }else y+=dist;

    return new Node(x, y);
}

 

 

나머지 상, 좌, 하도 같은 방식으로 진행하면 된다. 

 

 

 

👩‍💻 전체 코드 

// 오른쪽 이동 
public static Node moveRight(int x, int y, int d) {
    int dist = d%(2*(M-1));
    //현재 위치 기준 오른쪽에 남은 칸 = M-y-1
    if(M-y-1<dist) {
        dist-=M-y-1;
        if(M-1<dist) {
            dist-=M-1;
            y = dist;
        }else y = M-1-dist;
    }else y+=dist;

    return new Node(x, y);
}

// 왼쪽 이동 
public static Node moveLeft(int x, int y, int d) {
    int dist = d%(2*(M-1));
    //현재 위치 기준 왼쪽에 남은 칸 = y
    if(y<dist) {
        dist-=y;
        if(M-1<dist) {
            dist-=M-1;
            y = M-1-dist;
        }else y = dist;
    }else y-=dist;

    return new Node(x, y);
}

// 아래쪽 이동 
public static Node moveDown(int x, int y, int d) {
    int dist = d%(2*(N-1));
    //현재 위치 기준 아래쪽에 남은 칸 = N-x-1
    if(N-x-1<dist) {
        dist-=N-x-1;
        if(N-1<dist) {
            dist-=N-1;
            x = dist;
        }else x = N-1-dist;
    }else x+=dist;

    return new Node(x, y);
}

// 위쪽 이동 
public static Node moveUp(int x, int y, int d) {
    int dist = d%(2*(N-1));
    //현재 위치 기준 위쪽에 남은 칸 = x
    if(x<dist) {
        dist-=x;
        if(N-1<dist) {
            dist-=N-1;
            x = N-1-dist;
        }else x=dist;
    }else x-=dist;

    return new Node(x, y);
}

 

 

 

 

 

참고 문제 

https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석