BOJ 10875 뱀

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

10875번: 뱀

문제는 단순하다. 지나온 정점을 다시 지나가려 하거나, 격자판 밖으로 나가면 죽는다!!

그런데.. 격자판의 크기가.. 2억 * 2억 이다. vis배열을 당연히 사용할 수 없다.

나의 굳어버린 머리는 vis배열 없이는 도저히 해결할 수 없을 것 같았다..

지나간 곳만 저장하는 sparse table을 이용해볼까 했는데.. 모든 정점을 지나가면?? 결국 vis배열을 사용한 것과 같아서 안된다고 생각했다.

여기서 간과한 부분이 있었다.. 

바로 방향전환은 최대 1000번(input 값의 N) 이라는 것이다.

따라서, 지나간 선분목록을 배열에 저장해놓고, 새로운 선분을 그릴때마다 지나온 선분과 일일히 대조해 보아도 O(N*2)면 해결이 되는 것이었다!!!

2억*2억에 빠져서 N의 크기를 제대로 확인도 안해보고 인터넷 검색부터 해보다니.. 아직 갈길이 멀었다.

 

이제 문제는 굉장히 간단해졌다. 단순히, 선분과 선분이 교차하는지만 구현을 하면 간단히 통과 가능한 문제로 바뀌었다.

구현 자체 난이도는 골드 정도의 수준이다. 선분 교차 확인도 딱히 알고리즘을 사용하지 않고 하나하나 확인해도 통과 가능하다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

typedef pair<int, int> ii;
typedef pair<ii, ii> iiii;

typedef long long ll;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int L, N;
    cin >> L >> N;

    // 죽기까지 걸린 시간
    ll ans = 0;

    // 현재 위치
    ii now = ii(0, 0);

    // 현재 방향
    int dir = 0;

    // 그동안 지나온 선분목록
    vector<iiii> vec;
    while (N-- >= -1) {
        ii next;
        // 회전을 끝낸 마지막 전진일때
        if (N == -1) {
            // 진행가능거리를 최대진행가능거리 + 1 로 해준다.
            next = ii(now.first + dx[dir] * 200000001, now.second + dy[dir] * 200000001);
        }
        // 진행 가능 거리를 인풋으로 받아올 때.
        else {
            int mv; cin >> mv;
            next = ii(now.first + dx[dir] * mv, now.second + dy[dir] * mv);
        }        

        // 죽었는가??
        bool flag = false;

        // 죽기까지 이동한 최소거리
        int minTemp = 2147483647;


        // 닿는 선분이 있는지 확인
        for (iiii line : vec) {
            ii lineS = line.first, lineE = line.second;

            // 현재의 움직임이 위아래로 이루어질 때
            if (dir % 2) {
                // 현재 확인중인 선분의 좌우 폭 사이에 지금 그은 라인의 x좌표가 포함될 때
                if (min(lineS.first, lineE.first) <= now.first && now.first <= max(lineS.first, lineE.first)) {
                    // 현재 긋는 선분이 아래에서 치고 올라가는 형태
                    if (now.second < min(lineS.second, lineE.second) && dir == 3) {
                        // 안닿은 경우
                        if (next.second < min(lineS.second, lineE.second)) {
                            continue;
                        }
                        // 닿은 경우
                        else {
                            flag = true;
                            // 이동 가능한 거리 갱신
                            minTemp = min(minTemp, abs(min(lineS.second, lineE.second) - now.second));
                        }
                    }
                    // 현재 긋는 선분이 위에서 아래로 내려가는 형태
                    else if (now.second > max(lineS.second, lineE.second) && dir == 1) {
                        // 안닿은경우
                        if (next.second > max(lineS.second, lineE.second)) {
                            continue;
                        }
                        // 닿은 경우
                        else {
                            flag = true;
                            // 이동 가능한 거리 갱신
                            minTemp = min(minTemp, abs(max(lineS.second, lineE.second) - now.second));
                        }
                    }
                }
            }
            // 현재의 움직임이 좌우로 이루어질 때
            else {
                // 현재 확인중인 선분의 위아래 사이에 지금 그은 라인의 y좌표가 포함일 때
                if (min(lineS.second, lineE.second) <= now.second && now.second <= max(lineS.second, lineE.second)) {
                    // 현재 긋는 선분이 왼쪽에서 오른쪽으로 갈때
                    if (now.first < min(lineS.first, lineE.first) && dir == 0) {
                        // 안닿은 경우
                        if (next.first < min(lineS.first, lineE.first)) {
                            continue;
                        }
                        // 닿은 경우
                        else {
                            flag = true;
                            // 이동 가능한 거리 갱신
                            minTemp = min(minTemp, abs(min(lineS.first, lineE.first) - now.first));
                        }
                    }
                    // 현재 긋는 선분이 오른쪽에서 왼쪽으로 갈때
                    else if (now.first > max(lineS.first, lineE.first) && dir == 2) {
                        // 안닿은 경우
                        if (next.first > max(lineS.first, lineE.first)) {
                            continue;
                        }
                        // 닿은 경우
                        else {
                            flag = true;
                            //이동 가능한 거리 갱신
                            minTemp = min(minTemp, abs(max(lineS.first, lineE.first) - now.first));
                        }
                    }
                }
            }
        }

        // 닿는 선분이 있었다면
        if (flag) {
            // 경계선을 넘어서 죽은 경우와의 일반화를 위해 보정치 -1 (닿는 선분이 있을때의 거리계산은 도착지 포함, 경계선을 넘은 경우는 도착지 불포함이라 도착지를 포함한 이 경우에 -1을 해주어야 일반화가 됨)
            ans += minTemp-1;
            break;
        }

        // 마지막으로 경계선을 넘어갔는지 확인
        if (next.first > L) {
            ans += abs(L - now.first);
            break;
        }
        else if (next.first < -L) {
            ans += abs(-L - now.first);
            break;
        }
        else if (next.second > L) {
            ans += abs(L - now.second);
            break;
        }
        else if (next.second < -L) {
            ans += abs(-L - now.second);
            break;
        }

        // 안죽은 경우 아래의 코드 실행

        // 벡터에 현재 선분 저장하고
        vec.push_back(iiii(now, next));

        // 이동거리 저장
        ans += (abs(next.first - now.first) + abs(next.second - now.second));

        // 현재 위치 갱신 후
        now = next;

        // 방향 돌리기
        char td; cin >> td;
        if (td == 'L') {
            dir -= 1;
            if (dir == -1) dir = 3;
        }
        else if (td == 'R') {
            dir += 1;
            dir %= 4;
        }
    }
    cout << ans+1;

    return 0;
}