백준 10158번: 개미

단순 문제풀이에 따른 시간초과와 이에 따른 시간복잡도 개선 방법에 대해 생각해볼 수 있는 문제입니다.

 

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

---

풀이

    public static void solve01(int w, int h, int x, int y, int t) {
        int velX = 1;
        int velY = 1;

        while (t-- > 0){
            if(x == w) velX = -1;
            else if (x == 0) velX = 1;
            if(y == h) velY = -1;
            else if (y == 0) velY = 1;
            x += velX;
            y += velY;
        }
        System.out.println(x + " " + y);
    }

단순하게 가로(w), 세로(h), 현재 좌표 x(x), 현재 좌표 y(y), 진행시간(t)를 매개변수로 받아 풀이를 진행한 코드입니다.

예제 입력에 따른 예제 출력이 맞아 정상적으로 잘 작동하는듯 보입니다.

 

하지만, 이 문제에는 0.15초의 시간 제한이 존재하고, 계산할 시간 t의 범위는 1 <= t <= 200,000,000으로 어마어마한 계산 시간을 입력받게 됩니다.

 

작성한 코드의 시간 복잡도는 반복문 하나로 입력받은 진행시간동안만 실행되면 되므로 O(T)라고 할 수 있습니다.

그런데 입력 시간이 200,000,000 ? 시간 제한 초과를 피할 수 없습니다.

 

꽤나 단순한 문제라고 생각했고, 풀이방법또한 단순해 이 코드에서 어떻게 시간 최적화를 할 수 있을까에 대한 고민이 필요합니다.

특히 어떠한 정렬 알고리즘이 이용된것도 아니기에, 단순 특정 알고리즘에 대한 시간복잡도를 외워 모든 문제를 풀이하는 접근방법으로는 어떠한 방법도 적용시킬 수 없습니다.

 

시간복잡도, 공간복잡도를 떠나 규칙(패턴)을 찾는 방식으로 접근방식을 추가해볼 필요가 있습니다.

 

첫 예제 입력인 좌표 (4, 1)에서 시작했다고 가정합니다.

T=24 지점에서 원점좌표 (4, 1)로 돌아오며, 진행방향도 같은 모습을 볼 수 있습니다.

 

그렇지만, 이런식의 문제에 대해 규칙, 패턴을 찾아야 할 때 항상 그림을 그려 확인할 수는 없습니다.

따라서, 이 또한 코드로 작성해봅니다.

boolean[][] visitedUpperRight = new boolean[h + 1][w + 1];
boolean[][] visitedUpperLeft = new boolean[h + 1][w + 1];
boolean[][] visitedLowerRight = new boolean[h + 1][w + 1];
boolean[][] visitedLowerLeft = new boolean[h + 1][w + 1];

while(t-- > 0){
    x += velX;
    y += velY;

    if(velX == 1 && velY == 1){
        if(visitedUpperRight[x][y]){

        }
    }else if(velX == -1 && velY == 1){
        if(visitedUpperLeft[x][y]){

        }
    }else if(velX == -1 && velY == 1){
        if(visitedLowerRight[x][y]){

        }
    }else if(velX == 1 && velY == -1){
        if(visitedLowerLeft[x][y]){}
    }


}

이런식으로 우상단, 좌상단, 우하단, 좌하단 진행마다 방문했던 좌표일때 특정 코드를 실행하게 하면 될 것 같습니다.

하지만, 여기에도 조심해야할 부분이 있습니다.

 

이미 이렇게 작성한 코드에서 주기를 찾는동안 시간도 메모리도 복잡도가 O(W * H)로 가로와 세로 너비가 2<= W, H <= 40,000임을 생각해본다면 최대 40,000의 가로, 세로 넓이를 입력 예제로 사용할 때 40,000 * 40,000 * 1byte(boolean이므로) = 1,600,000,000 byte의 공간을 사용하게 되어버리고 1.6GB의 배열은 메모리 제한(256MB)을 초과해버리게 됩니다.

 

새로운 접근방법이 필요합니다.

 

어차피 가로, 세로 이동은 서로에 영향을 주지 않으니 가로, 세로를 분리하는 쪽으로 접근해봅니다.

 

가로, 세로 각각 개미는 (2*w) 만큼 움직이면 제자리로 돌아옵니다.(같은 진행방향, 같은 좌표)

그러므로, (2*w)는 계속 반복되므로 생략해서 계산을 단축하고 싶습니다.

이때 모듈로(%: 값으로 나눈 나머지)를 이용하면 됩니다.

 

즉 '0~6까지의 가로축, 0좌표에서 개미가 300시간을 움직인 뒤 어느 좌표에 위치해있나?'를 계산하고 싶다면

주기를 제외한 이동시간 = 300%(2*6) = 300%12 = 0시간 이므로 개미는 제자리인 0좌표에 있음을 알 수 있습니다. 한시간 더 움직였다면 ?

주기를 제외한 이동시간 = 301%(2*6) = 300%12 = 1시간 이므로 0좌표에서 1시간을 더 이동한 1좌표에 개미가 있음을 알 수 있습니다.

이를 x, y좌표에 대해 코드로 아래와 같이 작성할 수 있습니다.

int velX = 1;
int velY = 1;

int timeX = t%(2*w);
int timeY = t%(2*h);

while(timeX-- > 0){
    if(x == w) velX = -1;
    else if(x == 0) velX = 1;
    x += velX;
}

while(timeY-- > 0){
    if(y == h) velY = -1;
    else if(y == 0) velY = 1;
    y += velY;
}

 

주기를 구하는 과정을 생략해버림으로써 시간복잡도가 O(max(w, h)) (w나 h중 최댓값)으로 최적화 되었습니다.

이대로 작성하면 시간제한을 통과할 수 있게 됩니다.

 

추가로, 이 시간복잡도를 O(1)까지 줄여버릴 수 있습니다.

 

지금까지의 방식은 '주기를 제외한 이동시간을 구해 개미의 원래좌표에서 더 이동하는 방식'이었습니다.

이를 '애초에 원래 이동한 좌표까지의 시간까지 더한 시간으로부터 주기를 제외한 이동시간을 개미의 최종좌표로 변환하는 방식'으로 바꾸는 것입니다.

 

개미가 원래 0~6길이의 좌표 위에서 (3, 0) 좌표에 위치해있었다고 가정합니다.

301시간만큼 이동한 좌표는 '(원래 이동한 좌표까지의 시간 = 3 + 301 시간) % (2 * w)'으로 계산하는 것입니다.

304%(2*6) = 304%12 = 4

개미는 (4, 0) 좌표에 있음을 알 수 있습니다.

 

한가지 변수가 있습니다. 개미의 원래 좌표가 (6, 0) 좌표라고 가정해봅니다.

301 시간만큼 이동한 좌표는 같은 방식으로, 307%12 = 7 입니다.

그런데 좌표길이는 0~6이므로 개미가 (7, 0)좌표위에 있을 수는 없습니다.

(6, 0)좌표 보다 더 이동하면 역방향으로 이동해야 하므로

2*w-x로 수식을 고쳐주면, 12-7로 (5, 0) 추가된 1좌표만큼 역방향으로 이동한 값을 얻을 수 있습니다.

 

이를 x,y 좌표 모두 코드로 표현하면

int x = (p + t) % (2 * w);
if (x > w) x = 2 * w - x;

int y = (q + t) % (2 * h);
if (y > h) y = 2 * h - y;

이렇게 바꿔 쓸 수 있습니다.

위처럼 작성하면 최종 시간복잡도는 O(1)로 줄어들게 됩니다.

 

O(T): 최악의 경우 2억 → O(max(w, h)): 최악의 경우 8만 → O(1)으로 최적화한 것 입니다.

 

---

 

1번에서 2번까지는 어떻게든 시간제한안에 계산을 밀어넣어야 하므로 해결법을 찾는다고 가정해도, 3번 O(1)로 줄이는 것은 확실히 쉽지 않습니다.

우선은 패턴을 찾아 최적화 하는 방법이 있음을 숙지해두는 것이 좋을 것 같습니다.