BOJ#10875 뱀

BOJ#10875 뱀

* 문제

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

* 풀이

※ 문제 풀 때 주의할 점

주어진 입력의 크기를 잘 살펴봅시다. L <= 10^8이므로 

L은 1억이고 맵 사이즈는? (2억+1) * (2억+1)

맵 사이즈가 작다면 뱀 머리 경로를 따라가면서 visited배열을 써서 쉽게 풀 수 있겠습니다만,

이 문제는 무턱대로 map 크기만큼 visited 배열을 만들었다가는 런타임 에러를 맞이하게 될 것입니다.(Out of memory)

이 문제는 L보다는 N을 사용해서 풀어야 합니다. (N <= 1,000)

O(N^2)이라고 해봤자 1,000,000 이니까 생각보다 빠르게 풀 수 있겠죠

※ 알고리즘

1. 뱀의 경로는 선분들의 모임이라고 생각 가능

2. 수평 혹은 수직으로 이루어진 선분들 사이의 교차 문제

   → 초기에 경계선 4개를 추가해준다.

3. 뱀 이동 정보를 하나씩 입력 받으면서, 저장된 선분들과 충돌 여부를 체크한다.

   → 단, 모든 명령이 끝난 시점에도 뱀이 충돌하지 않을 수 있으니, 마지막에는 긴 임의의 선분을 추가해서 뱀이 충돌할 수 있게 한다.

   → 현재 방향(curDir)과 위치(curRow, curCol)에서 최대로 이동할 수 있는 시간을 구한다.

   → 구한 시간이 입력받은 뱀 이동 시간보다 같거나 작으면? 충돌

   → 충돌하지 않았으면, 현재 선분을 생성한 후 선분들의 모임에 추가한다.

   → 반복

4. N <= 1000이므로 O(N^2)안에 해결 가능

↓ 테스트 케이스 보기 (클릭) ↓

3

4

1 L

2 L

1 L

2 L

=> 6

3

4

1 L

2 L

2 L

1 L

=> 8

TestCase #1

3

4

2 L

2 L

1 L

5 R

=> 7

TestCase #2

3

3

2 L

4 L

4 R

=> 6

TestCase #3

3

3

2 R

1 R

10 R

= 9

TestCase #4

3

3

2 R

10 L

4 R

= 6

TestCase #5

3

3

2 L

10 L

4 R

= 6

TestCase #6

3

3

10 L

4 L

4 R

= 4

TestCase #7

3

3

2 L

4 L

4 R

= 6

TestCase #8

3

4

2 L

2 L

1 L

5 R

= 7

TestCase #9

3

4

2 R

2 R

1 R

5 L

= 7

TestCase #10

3

5

2 R

3 L

1 L

2 L

10 L

= 9

TestCase #11

3

5

2 R

3 R

1 R

2 R

10 L

= 9

TestCase #12

3

5

2 R

3 R

1 R

2 L

10 L

= 13

TestCase #13

3

8

3 R

3 R

6 R

6 R

6 R

2 R

10 L

10 R

= 32

TestCase #14

3

4

3 R

3 R

3 R

3 R

= 12

TestCase #15

3

4

3 R

3 R

3 R

2 R

14

TestCase #16

100000000

4

2 L

2 L

1 L

5 R

7

TestCase #17

1

6

1 L

1 L

2 L

2 L

2 L

2 L

9

TestCase #18

3

8

2 L

2 L

3 L

4 L

4 L

5 L

2 L

7 L

23

TestCase #19

3

8

2 L

2 L

3 L

4 L

4 L

10 L

2 L

7 L

21

TestCase #20

8

11

1 L

4 R

1 R

8 L

1 L

8 R

1 R

8 L

1 L

6 L

10 R

40

TestCase #21

3

1

1 L

5

TestCase #22

3

1

1 R

5

TestCase #23

3

2

1 R

1 R

7

TestCase #24

3

2

1 R

1 L

5

TestCase #25

3

1

10 L

4

TestCase #26

3

3

2 L

4 L

4 R

6

TestCase #27

3

3

1 R

1 R

10 L

7 

TestCase #28

3

3

1 R

1 L

10 L

5 

TestCase #29

3

0

4

TestCase #30

3

14

3 L

1 L

3 R

1 R

3 L

1 L

6 L

1 L

5 R

1 R

4 L

3 L

1 L

2 L

22

TestCase #31

3

16

3 L

1 L

3 R

1 R

3 L

1 L

6 L

6 L

1 L

5 R

1 R

5 L

4 L

1 L

3 R

1 R

49

TestCase #32

3

16

3 L

1 L

3 R

1 R

3 L

1 L

6 L

6 L

1 L

5 R

1 R

5 L

4 L

1 L

3 R

2 R

46

TestCase #33

3

17

3 L

1 L

3 R

1 R

3 L

1 L

6 L

6 L

1 L

5 R

1 R

5 L

4 L

1 L

3 R

1 R

3 L

49

TestCase #34

3

1

1 L

5

TestCase #35

1

1

1 L

3

TestCase #36

3

5

3 L

1 L

6 L

1 L

2 L

14

TestCase #37

3

5

3 L

1 L

6 L

1 L

2 R

17

TestCase #37

3

5

3 L

1 L

6 L

1 L

3 R

14

TestCase #37

3

5

3 L

1 L

6 L

1 L

100000 R

14

TestCase #38

100000000

5

100000000 L

100000000 L

200000000 L

199999999 L

199999999 L

=> 899999997

TestCase #39

3

5

3 L

3 L

6 L

5 L

5 L

=> 24

※ 두 선분의 교차를 체크하는 알고리즘에 대해..

처음에는 외적을 이용해서 풀다가 long 범위를 넘어버리는 골치 아픈 문제 때문에 한참 헤매다가

최근 다른 분들의 소스코드를 참고하여 풀게 되었습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/2cce99f19aa13fd7a1aec3ff1524a402f9b7c08a/BOJ%2310875_Snake/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * BOJ#10875 뱀
 * https://www.acmicpc.net/problem/10875
 */

public class Main {

    static final int LEFT = 0;
    static final int UP = 1;
    static final int RIGHT = 2;
    static final int DOWN = 3;

    static final int HORIZON = 0;
    static final int VERTICAL = 1;

    static final int ROTATE_LEFT = -1;
    static final int ROTATE_RIGHT = 1;

    static final int[] dRow = {0, -1, 0, 1};
    static final int[] dCol = {-1, 0, 1, 0};

    static final int INF = 1_000_000_000;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int L = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        int size = 2 * L + 1;

        int curRow = L;
        int curCol = L;
        int curDir = RIGHT;

        // 4개의 경계선 입력
        ArrayList<Line> lineList = new ArrayList<>();   // line 저장 리스트
        lineList.add(new Line(-1, size, size, size));           // 오른쪽 경계선
        lineList.add(new Line(size, -1, size, size));           // 아래쪽 경계선
        lineList.add(new Line(-1, -1, -1, size));  // 위쪽 경계선
        lineList.add(new Line(-1, -1, size, -1));  // 왼쪽 경계선

        // input & solve
        int time;
        int rotateDir;
        long collisionTime = 0L;    // 충돌 시간
        for (int i = 0; i <= N; i++) {

            if (i < N) {

                StringTokenizer st = new StringTokenizer(br.readLine());

                time = Integer.parseInt(st.nextToken());
                rotateDir = st.nextToken().charAt(0) == 'L' ? ROTATE_LEFT : ROTATE_RIGHT;
            } else {

                // 마지막에 긴 선분을 하나 추가하여 뱀이 무조건 충돌할 수 있게 해준다
                time = INF;
                rotateDir = ROTATE_LEFT;
            }

            int t = INF;

            // 현재 선분과 저장된 선분들 충돌 검사, 가장 짧은 충돌시간을 찾는다
            //for (Line prevLine : lineList) {
            for (int l = 0; l < lineList.size() - 2; l++) {

                Line prevLine = lineList.get(l);

                switch (curDir) {

                    case LEFT:

                        if ((prevLine.dir == HORIZON && prevLine.row1 == curRow && curCol > prevLine.col2)
                                || (prevLine.dir == VERTICAL && curRow >= prevLine.row1 && curRow <= prevLine.row2 && curCol > prevLine.col2)) {

                            t = Math.min(t, curCol - prevLine.col2);
                        }
                        break;

                    case UP:

                        if ((prevLine.dir == VERTICAL && prevLine.col1 == curCol && curRow > prevLine.row2)
                                || (prevLine.dir == HORIZON && curCol >= prevLine.col1 && curCol <= prevLine.col2 && curRow > prevLine.row2)) {

                            t = Math.min(t, curRow - prevLine.row2);
                        }
                        break;

                    case RIGHT:

                        if ((prevLine.dir == HORIZON && prevLine.row1 == curRow && curCol < prevLine.col1)
                                || (prevLine.dir == VERTICAL && curRow >= prevLine.row1 && curRow <= prevLine.row2 && curCol < prevLine.col1)) {

                            t = Math.min(t, prevLine.col1 - curCol);
                        }
                        break;

                    case DOWN:

                        if ((prevLine.dir == VERTICAL && prevLine.col1 == curCol && curRow < prevLine.row1)
                                || (prevLine.dir == HORIZON && curCol >= prevLine.col1 && curCol <= prevLine.col2 && curRow < prevLine.row1)) {

                            t = Math.min(t, prevLine.row1 - curRow);
                        }
                        break;
                }
            }

            // 충돌한 경우
            if (t <= time) {

                collisionTime += t;

                System.out.println(collisionTime);
                return;
            }

            // 충돌하지 않은 경우
            collisionTime += time;

            // 현재 선분 생성
            int nextRow = curRow + dRow[curDir] * time;
            int nextCol = curCol + dCol[curDir] * time;

            Line curLine = new Line(curRow, curCol, nextRow, nextCol);
            lineList.add(curLine);

            // 다음 진행 설정
            curRow = nextRow;
            curCol = nextCol;
            curDir = (curDir + rotateDir + 4) % 4;
        }
    }
}

class Line {

    int row1, col1, row2, col2;
    int dir;

    Line(int row1, int col1, int row2, int col2) {

        this.row1 = row1;
        this.col1 = col1;
        this.row2 = row2;
        this.col2 = col2;

        setDirection();
        setPoint();
    }

    private void setDirection() {

        // HORIZON
        if (this.row1 == this.row2) {

            this.dir = 0;
        }
        // VERTICAL
        else {

            this.dir = 1;
        }
    }

    private void setPoint() {

        if (row1 > row2) {

            row1 ^= row2;
            row2 ^= row1;
            row1 ^= row2;
        }

        if (col1 > col2) {

            col1 ^= col2;
            col2 ^= col1;
            col1 ^= col2;
        }
    }
}