[ 백준 10875 ] 뱀 (C++)

백준의 뱀(10875) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 문제를 가장 쉽게 해결할 수 있는 방법으로 접근해보자.

뱀이 한번이라도 지나온 좌표들에 대해서는 체크해주면서 입력에 따른 방향으로 회전시키면서 하나하나 좌표들을 확인하면서

진행한다면 쉽게 답을 구할 수 있을 것이다.

하지만 ! 이렇게 구현한다면 시간초과를 받게 된다.

왜냐하면, 주어진 맵의 최대 크기는 2 * L + 1 이므로, 2억 X 2억 짜리 맵이 생성될 수 있고, 회전 할 때 마다 좌표 하나하나 씩

확인한다면, 2 x 10^8 짜리 칸을 10^3 번 만큼 체크해야 되는 상황이 발생하기 때문에 시간초과가 발생하게 된다.

따라서 좌표를 하나하나 체크하는 방법으로 문제를 해결할 수는 없다. 그래서 본인은 선분을 기준으로 체크해주었다.

지금부터 본인이 구현한 선분을 관리하는 방법과 어떤 경우에 충돌이 발생해서 뱀이 죽게되는지에 대해서 알아보자.

먼저, 본인은 선분을  { 시작 x좌표 , 마지막 x좌표, 시작 y좌표, 마지막 y좌표, 선분의 모양 } 이렇게 5개의 데이터를 구조체로

만들어서 선분을 관리해 주었다.

struct LINE
{
    int x;
    int y;
    int xx;
    int yy;
    int Shape;
};

이렇게 위와 같은 구조체를 선언해서 관리해주었다.

'선분의 모양' 이라는 것은 2가지가 존재할 수 있다. | 이와 같이 세로로 긴 형태, ㅡ 와 같이 가로로 긴 형태 2가지가 존재할

수 있다. 이 선분의 모양은 좌표값들을 비교해서 구할수도 있지만 본인은 방향을 통해서 구해주었다.

만약 현재 방향이 동쪽 혹은 서쪽 이라면 ㅡ 와 같이 가로로 긴 형태가 될 것이고, 현재 진행방향이 남쪽 혹은 북쪽이라면

| 와 같이 세로로 긴 형태가 될 것이다. 이렇게 방향을 통해서 선분의 형태를 정해주었다.

Shape가 0일 때는 'ㅡ' 형태를, Shape가 1일 때는 '|' 형태를 의미하도록 설정해 주었다.

또한, 선분을 관리하는 구조체에 '시작 / 마지막 x좌표 , y좌표' 가 존재하는데 무조건 ! 시작 좌표가 더 작도록 설정해 주었다.

무슨말인지 아래의 그림을 통해서 알아보자.

위와 같이 2개의 선분을 한번 봐보자.

먼저, 파랑색 선분 같은 경우 동쪽으로 향하고 있다. 동쪽으로 향할 경우, y좌표는 변함이 없고 x좌표만 증가하게 된다.

위의 맵의 가장 왼쪽 상단에 좌표를 (0, 0)이라고 가정한다면, 파랑색선분은 (0, 0)과 (2, 0)을 잇는 선분이 될 것이다.

위에 선언해 놓은 구조체에 선분을 담는다면 { 0, 0, 2, 0, 0 } 으로 들어가게 될 것이다.

두 번째로, 초록색 선분 같은 경우 북쪽으로 향하고 있다. 북쪽으로 향할 경우, x좌표는 변함이 없고 y좌표만 증가하게 된다.

위의 맵의 가장 우측 하단에 좌표를 (0, 0)이라고 가정한다면, 초록색 선분은 (0, 0)과 (0, 2)를 잇는 선분이 될 것이다.

위에 선언해 놓은 구조체에 선분을 담는다면 { 0, 0, 0, 2, 1 } 로 들어가게 될 것이다.

그럼 위의 선분과는 반대 방향으로 향하고 있는 2개의 선분을 한번 봐보자.

먼저, 파랑색 선분 같은 경우 서쪽으로 향하고 있다. 서쪽으로 향할 경우, y좌표는 변함이 없고 x좌표만 감소하게 된다.

위의 맵에서 파랑색 동그라미 점을 (0, 0)이라고 가정한다면, 파랑색 선분은 (0, 0)과 (-2, 0)을 잇는 선분이 될 것이다.

그럼 위의 선분을 구조체에 담는다면 { 0, 0, -2, 0, 0 } 이 들어가게 될 것이다.

하지만 ! 본인은 무조건 더 작은 좌표를 시작점에 담아준다고 했었다. 어차피 선분이라는 것이 처음 선분이 만들어 질 때만

어느 방향으로 움직이냐에 따라서 시작점과 마지막점이 더 크고 작다는 관계가 있을 뿐이지, 결국 선분이 완성이 되고 나면

진행방향은 크게 의미가 없다. 그래서 무조건 더 작은 좌표들을 시작점으로 만들어 주었다.

즉 위의 파랑색 선분을 구조체에 담는다면 { 0, 0, -2, 0, 0 } 이 아닌, { -2, 0, 0, 0, 0 } 으로 들어가게 된다.

두번째로 초록색 선분을 한번 봐보자. 초록색 선분 같은 경우는 남쪽으로 향하고 있다.

남쪽으로 향할 경우, x좌표는 변함이 없고, y좌표만 감소하는 형태이다. 위의 초록색 점을 (0, 0)이라고 가정한다면,

초록색 선분은 (0, 0)과 (0, -2)를 잇는 선분이 될 것이다. 하지만 구조체에 담을 때는 { 0, 0, 0, -2, 1 } 이 아닌,

{ 0, -2, 0, 0, 1 } 로 들어가게 만들어 주었다.

그럼 ! 이렇게 선분을 만들었다면 어떤 경우에 충돌하는지에 대해서 알아보자.

본인은 크게 4가지 경우로 나누어서 구현해 주었다.

1. 내가 지금 만들려는 선분이 'ㅡ'와 같이 가로로 긴 형태의 선분일 때

    1. 비교하려는 선분이 'ㅡ'와 같은 형태인 선분일 때

    2. 비교하려는 선분이 ' | ' 와 같은 형태인 선분일 때

2. 내가 지금 만들려는 선분이 ' | '와 같이 세로로 긴 형태의 선분일 때

    1. 비교하려는 선분이 'ㅡ'와 같은 형태인 선분일 때

    2. 비교하려는 선분이 ' | '와 같은 형태인 선분일 때

그럼 이 4가지 경우 하나하나 어떻게 처리하면 되는지 구체적으로 알아보자.

[ 지금부터는 설명을 편하게 하기 위해서 아래의 설명에서 사용할 변수들 몇가지만 소개하겠습니다. ]

내가 지금 만들려는 선분 : (x, y) 에서 (nx, ny) 를 잇는 선분을 만들 것이다. (무조건 ! x < nx && y < ny)

지금 비교하려는 선분 : (rx, ry) 에서 (rxx, ryy)를 잇는 선분과 비교할 것이다. (무조건 ! rx < rxx && ry < ryy)

Case 1-1) "나는 가로선분이고, 비교하려는 선분 또한 가로 형태의 선분인 경우"

내가 지금 만들려는 선분이 'ㅡ' 형태인데, 비교하는 선분 또한 'ㅡ'형태인 경우이다.

그럼 쉽게 생각해서 겹치는 경우는 2가지 경우밖에 존재하지 않는다.

위의 그림과 같이 2가지 경우가 존재한다. 빨강색 선분이 비교하려는 선분이라고 가정했을 때,

동쪽으로 움직일 때는 파랑색 선분과 , 서쪽으로 움직일 때는 초록색 선분과 같이 겹치는 경우가 발생할 수 있다.

위의 상황에서 파랑색 선분의 (x, y)(nx, ny), 초록색 선분의 (x, y)(nx, ny), 빨강색 선분의 (rx, ry)(rxx, ryy) 를 생각하자 !

그림으로 선분의 좌표만 나타내면 다음과 같다. (어차피 y좌표는 동일하므로 생략하겠습니다.)

먼저 1-1)Case의 경우 겹치기 위해서 조건이 하나 필요하다. 바로 ' y = ry ' 라는 조건이다.

y축이 다르다면, 절대로 'ㅡ' 형태를 가진 2개의 선분은 겹칠 수가 없다. 즉, 위의 조건이 부합한다면 두 번째 조건을 생각해보자.

먼저 동쪽으로 움직이는 파랑색 선분을 보자. 파랑색 선분은 언제 빨강색 선분과 겹치게 될까 ??

바로, ( x < rx && rx <= nx) 인 경우이다. 말로 표현해보면, "지금 내가 만들려는 선분의 시작좌표가 비교하려는 선분의 시작좌표보다 작고, 만들려는 선분의 마지막 좌표가 비교하려는 선분의 시작좌표보다 크거나 같다면 충돌 !" 이 되는 것이다.

두 번째로 초록색 선분을 보자. 마찬가지로 'y = ry'라는 조건이 성립해야 충돌의 가능성이 있는지 판단해 볼 가치가 있다.

초록색 선분과 빨강색 선분이 겹치는 경우를 생각해보면 다음과 같다.

( x <= rxx &&rxx < nx) 인 경우이다. 위의 그림을 보고 그대로 받아들이고 생각해보면 쉽게 나올 수 있는 조건이다.

그럼 우리가 구해야 하는 것은 어차피 "몇 초 동안 움직일 수 있냐" 를 구해야 하는 것이기 때문에, 충돌이 난다고 해서

충돌이 났습니다 ! 라고 출력을 하고 끝내면 되는 상황이 아니라, 충돌이 나더라도 최대 몇 초 까지 움직일 수 있는지

계산해야 하기 때문에 몇 초 까지 움직일 수 있는지를 계산해보자.

파랑색 선분의 경우, rx - x 초 동안 움직일 수 있다. 초록색 선분의 경우 nx - rxx 초 동안 움직일 수 있다.

위의 그림과 같이 그 이상으로 움직여 버리면 뱀이 자신의 몸뚱아리와 충돌해서 죽어버리기 때문이다.

Case 1-2) " 나는 가로 형태의 선분인데, 비교하려는 선분은 세로 형태의 선분인 경우"

이 경우도 아래 그림과 같이 2가지 형태로 충돌이 가능하다.

위와 같이 동쪽으로 움직이면서 충돌하는 경우가 있고, 서쪽으로 움직이면서 충돌하는 경우도 존재한다.

먼저 좌표부터 적어보고 시작해보자.

이 경우 또한, 충돌을 하기 위해서 가장 우선적으로 성립해줘야 하는 조건이 하나 있다.

위의 파랑색 선분과 초록색 성분이 왜 빨강색 선분이랑 충돌을 하는지 생각을 해보자. 어떻게 하면 파랑색 선분과 초록색 선분이

충돌을 안했을 수 있었을까? 아마 2가지 경우가 있을 것이다.

                  [ 그림 1 ]                                                                                         [ 그림 2 ]

[그림 1]과 같이, 빨강색 선분을 지나지 않게 아예 빨강색 선분 위쪽으로 혹은 아래쪽으로 움직이는 형태라면 충돌이

일어날 가능성 조차 없게 된다. 또한, [ 그림 2] 처럼, 빨강색 선분을 지날 수도 있을 것 같은데, 막상 움직여보니 충돌을 하지

않는 형태로 존재할 수도 있을 것이다. 위의 그림과 같은 경우(예시로 몇 가지만 그려본 것입니다.) 충돌이 일어나지 않는다.

그래서 본인은 첫번째 경우를 다음과 같이 설정해주었다.

" Ry <= y && y <= Ryy" 무슨말인지 생각해보자. 이 조건문은 빨강색 선분보다 위로 가거나 아래로 가는 경우는 계산을 하지 않기

위해서 걸어준 조건문이다.

최소한 이런 형태가 나오기 위해서는, "내가 지금 만들려는 선분의 y 값이, 빨강색 선분의 y범위(rx ~ ryy) 사이에 있어야

충돌할 가능성이 있는지 판별해볼만 하다는 것이다.

물론 이 조건을 만족한다고 무조건 충돌을 하는 것이 아니다. [ 그림 2 ]와 같은 경우를 대비해서 또 한번의 판단을 해줘야 한다.

먼저 동쪽 방향으로 움직이고 있는 파랑색 선분을 생각해보자. 파랑색 선분과 빨강색 선분이 겹치기 위한 조건을 알아보자.

바로 "(x < rx && rx <= nx)" 일 경우, 충돌이 일어나게 된다. 빨강색 선분은 세로로 긴 형태의 선분이기 때문에 rx와 rxx의 값이

동일하다. 따라서 위의 조건문에 rxx가 들어가도 상관은 없다.

충돌하기 위해서는 "내가 만들려는 선분의 시작 x좌표가 비교하려는 선분의 x좌표보다 작고, 마지막 x좌표가 비교하려는 선분의

x좌표보다 크거나 같아야 한다."

반대로 초록색 선분의 경우는 "(x <= rx && rx < nx)" 라는 조건이 필요하다.

마찬가지로 충돌하는 그 거리를 계산해보자면 파랑색 선분의 경우 "rx - x" 초 만큼 움직일 수 있고, 초록색 선분의 경우

"nx - rx" 초 만큼 움직일 수 있게 된다.

여기까지 총 4가지 경우 중, 2가지 경우에 대해서 이야기를 해 보았다.

이제 남은것은 "내가 만들려는 선분이 세로 형태의 선분일 때" 에 대한 2가지 경우이다.

물론 계산해야 하는 조건문들은 조금씩 다르겠지만 원리가 위에서 길게 설명한 내용들과 동일하다.

그래서 나머지 2가지 경우에 대해서는 더 이상 설명하지 않겠다. 설명을 하다보면 중복된 내용만 계속해서 이야기하게 될 수도

있어서 굳이 안해도 될 것 같다.

지금까지 구한 내용들을 정리를 한번 해보고 마지막 단계로 넘어가자.

1. 좌표들을 체크하면서 관리하기에는 맵이 너무 크기 때문에 시간초과가 발생한다. 따라서 '선분'의 개념으로 접근하였다.

2. 선분은 처음 생성될 때만 방향이 존재하고, 생성된 이후에는 방향이 존재하지 않는다. 따라서, 무조건 더 작은 좌표를

    시작좌표로, 더 큰 좌표를 마지막 좌표로 설정해 주었다.

3. 내가 지금 만들려는 선분 vs 기존에 존재하는 선분을 비교하면서 충돌하는지 판단해 주었다.

    판단을 해야 하는 경우는 총 4가지 경우가 존재한다. 4가지 경우는 다음과 같다.

1. 내가 만들려는 선분이 'ㅡ' 형태이고, 비교하려는 선분이 'ㅡ' 형태일 경우

    1) y좌표가 동일해야 충돌을 할 가능성이 있는지 판단해 볼 만 하다.

    2) y좌표가 동일하다면

        1) 동쪽으로 움직일 경우, (x < rx && rx <= nx) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 rx - x초.

        2) 서쪽으로 움직일 경우, (x <= rxx && rxx < nx) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 nx - rxx초.

2. 내가 만들려는 선분이 'ㅡ' 형태이고, 비교하려는 선분이 '|' 형태일 경우

    1) (ry <= y && y <= ryy) 라는 조건이 성립해야 충돌을 할 가능성이 있는지 판단해 볼 만 하다.

    2) 위의 조건을 만족한다면

        1) 동쪽으로 움직일 경우, (x < rx && rx <= nx) 라는 조건이 성립해야 충돌. 이 떄 충돌시간은 rx - x초.

        2) 서쪽으로 움직일 경우, (x <= rx && rx < nx) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 nx - rx초.

3. 내가 만들려는 선분이 '|' 형태이고, 비교하려는 선분이 '|' 형태일 경우

    1) x좌표가 동일해야 충돌을 할 가능성이 있는지 판단해 볼 만 하다.

    2) x좌표가 동일하다면

        1) 남쪽으로 움직일 경우, (y <= ryy && ryy < ny) 라는 조건이 성립해야 충돌. 이 떄 충돌시간은 ny - ryy 초.

        2) 북쪽으로 움직일 경우, (y < ry && ry <= ny) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 ry - y 초.

4. 내가 만들려는 선분이 '|' 형태이고, 비교하려는 선분이 'ㅡ' 형태일 경우.

    1) (rx <= x && x <= rxx) 라는 조건이 성립해야 충돌을 할 가능성이 있는지 판단해 볼 만 하다.

    2) 위의 조건을 만족한다면

        1) 남쪽으로 움직일 경우, (y <= ry && ry < ny) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 ny - ry 초.

        2) 북쪽으로 움직일 경우, (y < ry && ry <= ny) 라는 조건이 성립해야 충돌. 이 때 충돌시간은 ry - y 초.

위와 같이 한번 간단하게 정리를 해보았다.

선분을 어떻게 만들 것이고, 어떤 경우에 충돌하는지 총 4가지 경우로 나눠서 모두 구해보았다.

그럼 이제 위의 내용에서 딱 한가지 내용만 더 추가하고, 가장 첫 시작단계와, 가장 마지막 단계를 진행해보자.

지금까지는 중간과정이였다....

본인은 위에서 계산한 "충돌시간"을 return 하는 함수를 하나 만들어주었다. 충돌을 한다면 위에서 계산한 충돌시간을 return,

충돌을 하지 않는다면 단순히 '-1'을 return 함으로써 충돌 하지 않았다는 것을 알려주었다.

그런데 ! 충돌을 한다고 해서 그 즉시, 해당 충돌시간을 return 해주게 되면 큰 문제가 발생하게 된다. 충돌이 발생하더라도

모든 선분을 다 비교해 봐야 하는 것이다. 왜 그런지 아래의 경우를 한번 살펴보자.

파랑색 선분이 현재 뱀의 진행방향이다. 빨강색 선분의 경우 기존에 만들어 져 있던 선분들이다.

밑에 숫자들은 vector에 들어 있는 순서라고 생각해보자. 즉, 오른쪽에 있는 빨강색 선이 더 먼저 만들어진 선분이라서,

vector를 앞에서 부터 순차적으로 탐색한다고 가정했을 때, 오른쪽 선분이 왼쪽 선분보다 더 빨리 계산하게 된다는 것이다.

우리는 눈으로 봐서 알겠지만, 위와 같이 움직일 경우, 뱀은 '2'번 선분과 충돌해서 죽게된다. 1번 선분까지 가지 못한다.

그런데 ! vector에서 1번 선분이 더 먼저 나온다는 이유로, 1번 선분과의 충돌시간을 계산해서 그대로 return 해 버린다면 ?

당연히 잘못된 계산일 것이다. 따라서 ! 충돌이 발생하더라도, 그 즉시 충돌시간을 계산해서 return 시키는 것이 아니라 모든 선분을 비교해 주어야 한다는 것이다. 그 후, 충돌시간이 가장 작은 값 (가장 작다라는 말은 더 빨리 만나서 더 빨리 충돌해서 더 빨리

죽는 경우를 의미한다.)을 계산해서 return 시켜주면 된다. 이 경우를 생각 못해서 한참을 헤맸었다...

우리는 지금까지 선분이 어떤 경우에 충돌하는지에 대해서 알아보았다. 그런데 문제는, 가장 초기에 선분이 어디있냐는 것이다.

맵의 가장 초기에 선분이 존재하는 것이 아니다. 왜냐하면 맵의 가장 초기는 뱀이 아직 움직임을 시작하지 않은 상태이기 때문에

선분이 하나도 없을 것이다. 그런데 어떻게 비교를 할까 ??

사실, 가장 초기에도 뱀이 죽을 수 있는, 즉 충돌을 비교해볼 만한 선분이 이미 맵에 존재한다. 바로 맵의 테두리 이다.

뱀이 아직 한번도 안 움직여서 뱀이 만들어 놓은 선분은 없지만, 뱀의 첫 움직임에서 만약 뱀의 범위를 벗어날 때 까지 움직인다면?

이렇게 되면 뱀은 죽게 된다. 즉, 맵의 4개의 테두리(맵은 사각형 형태이므로) 는 초기에 존재하는 선분이라고 볼 수 있다.

따라서, 뱀을 움직이기 전에, 선분을 넣어서 관리해주는 vector에 4개의 테두리를 넣어주었다.

이 후, 뱀이 충돌을 하지 않고 선분을 만들 수 있다면 계속해서 vector에 해당 선분을 넣어주었다.

그래서 모든 명령어를 무사하게 잘 끝냈다면 ? 뱀은 무한대로 살 수 있는 것일까 ? 명령어를 충돌없이 끝냈다는 이야기는

더 이상 뱀이 회전할 일이 없다는 이야기이다. 더 이상 움직이지 않는다는 것이 아니다. 즉, 가장 최종적으로 선택된 진행방향으로

움직일 것이다. 그 과정에서 뱀이 생성한 선분과 충돌할 수도 있고, 맵의 테두리까지 갈 수도 있다.

따라서 ! 모든 명령어들을 진행하면서 선분을 만들어주고 비교해주자. 충돌이 일어나서 뱀이 죽게되면 그대로 시간을 계산해서

출력해주면 끝이고, 그게 아니라면 마지막으로 한번 더 비교를 해줘야 한다. 이 때는 도착 좌표가 어디일까 ??

본인은 "맵의 최대범위 + - 1" 로 마지막 좌표를 설정해서 탐색해 주었다. 이렇게 되면 뱀이 무조건 죽게 된다. 왜냐하면 맵의

테두리가 존재하기 때문에 무조건 4개의 테두리 중 한개와는 겹칠 수 밖에 없게 된다.

이러한 과정이 필요하다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
using namespace std;
 
struct LINE
{
    int x;
    int y;
    int xx;
    int yy;
    int Shape;
};
 
int L, N, Min_Range, Max_Range;
vector<LINE> Route;
vector<pair<int, char>> Cmd;
 
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> L >> N;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        char c; cin >> c;
        Cmd.push_back(make_pair(a, c));
    }
}
 
int Make_Shape(int Dir)
{
    if (Dir == 0 || Dir == 1) return 0;
    else return 1;
}
 
int CheckMode(int Shape, int RShape)
{
    /* 내가 지금 움직임에 의해서 만드는 선분과 비교하려는 선분의 관계 구하기. */
    /* 만약 지금 내가 만드는 선분과 비교하려는 선분이 똑같이 가로 모양의 선분이다 = return 0 */
    /* 지금 내가 만드는 선분과 비교하려는 선분이 똒같이 세로 모양의 선분이다 = return 1 */
    /* 지금 내가 만드는 선분과 비교하려는 선분이 다르고, 나는 가로, 비교는 세로 선분일 경우 = return 2 */
    /* else return 3;*/
    if (Shape == RShape)
    {
        if (Shape == 0)return 0;
        else return 1;
    }
    else
    {
        if (Shape == 0 && RShape == 1) return 2;
        if (Shape == 1 && RShape == 0) return 3;
    }
}
 
int BoomCheck(int x, int y, int nx, int ny, int Rx, int Ry, int Rxx, int Ryy, int Dir, int LS)
{
    /* 2개의 선분이 충돌을 한다면 true를, 안한다면 -1을 반환하는 함수. */
    /* 가로 선분 = y좌표는 일정하고, x좌표만 바뀐다. */
    /* 세로 선분 = x좌표는 일정하고, y좌표만 바뀐다. */
    if (LS == 0)
    {
        /* 둘 다 동일하게 가로 선분일 경우 */
        if (y == Ry)
        {
            if (Dir == 0 && (x < Rx && Rx <= nx)) return abs(Rx - x);
            else if (Dir == 1 && (x <= Rxx && Rxx < nx)) return abs(nx - Rxx);
 
            return -1;
        }
        else return -1;
    }
    else if (LS == 1)
    {
        /* 둘 다 동일하게 세로 선분일 경우*/
        if (x == Rx)
        {
            if (Dir == 2 && (y <= Ryy && Ryy < ny)) return abs(ny - Ryy);
            if (Dir == 3 && (y < Ry && Ry <= ny)) return abs(Ry - y);
            return -1;
        }
        else return -1;
    }
    else if (LS == 2)
    {
        /* 나는 가로선분이고 , 비교는 세로선분인 경우 */
        if (Ry <= y && y <= Ryy)
        {
            if (Dir == 0 && (x < Rx && Rx <= nx)) return abs(Rx - x);
            else if (Dir == 1 && (x <= Rx && Rx < nx)) return abs(nx - Rx);
        }
        return -1;
    }
    else
    {
        /* 나는 세로선분이고 , 비교는 가로선분인 경우 */
        if (Rx <= x && x <= Rxx)
        {
            if (Dir == 2 && (y <= Ry && Ry < ny)) return abs(ny - Ry);
            else if (Dir == 3 && (y < Ry && Ry <= ny)) return abs(Ry - y);
        }
        return -1;        
    }
}
 
int Check(int x, int y, int nx, int ny, int Dir, int Shape)
{
    /* 선분의 충돌이 일어난다면 그 거리를 반환. 그게 아니라면 -1을 반환. */
    if (Dir == 1) swap(x, nx);
    if (Dir == 2) swap(y, ny);
    
    int Dist = 2e9;
    for (int i = 0; i < Route.size(); i++)
    {
        int Rx = Route[i].x;
        int Ry = Route[i].y;
        int Rxx = Route[i].xx;
        int Ryy = Route[i].yy;
        int RShape = Route[i].Shape;
        
        int Line_State = CheckMode(Shape, RShape);
        int Boom_Dist = BoomCheck(x, y, nx, ny, Rx, Ry, Rxx, Ryy, Dir, Line_State);
        if (Boom_Dist != -1) Dist = Min(Dist, Boom_Dist);
    }
 
    if (Dist == 2e9) return -1;
    else return Dist;
}
 
int Change_Direction(int Cur_Dir, char C)
{
    if (C == 'L')
    {
        if (Cur_Dir == 0) return 3;
        else if (Cur_Dir == 1) return 2;
        else if (Cur_Dir == 2) return 0;
        else if (Cur_Dir == 3) return 1;
    }
    else
    {
        if (Cur_Dir == 0) return 2;
        else if (Cur_Dir == 1) return 3;
        else if (Cur_Dir == 2) return 1;
        else if (Cur_Dir == 3) return 0;
    }
}
 
void Solution()
{
    Min_Range = -L -1;
    Max_Range = L + 1;
    Route.push_back({ Min_Range, -L, Min_Range, L, 1 });
    Route.push_back({ Max_Range, -L, Max_Range, L, 1 });
    Route.push_back({ -L, Max_Range, L, Max_Range, 0 });
    Route.push_back({ -L, Min_Range, L, Min_Range, 0 });
    
    int x = 0;
    int y = 0;
    int Dir = 0;
    long long Time = 0;
    bool Boom = false;
 
    for (int i = 0; i < N; i++)
    {
        int T = Cmd[i].first;
        char Change = Cmd[i].second;
        
        int nx = x + dx[Dir] * T;
        int ny = y + dy[Dir] * T;
        int Shape = Make_Shape(Dir);
 
        if (nx <= Min_Range || nx >= Max_Range || ny <= Min_Range || ny >= Max_Range) break;
        int Dist = Check(x, y, nx, ny, Dir, Shape);
        if (Dist != -1)
        {
            Boom = true;
            Time = Time + Dist;
            break;
        }
 
        Route.push_back({ Min(x, nx), Min(y, ny), Max(x, nx), Max(y, ny), Shape });
        x = nx;
        y = ny;
        Time = Time + T;
        Dir = Change_Direction(Dir, Change);
    }
    
    if (Boom == true)
    {
        cout << Time << endl;
        return;
    }
    
    int nx, ny;
    if (Dir == 0)
    {
        nx = Max_Range + 1;
        ny = y;
    }
    else if (Dir == 1)
    {
        nx = Min_Range - 1;
        ny = y;
    }
    else if (Dir == 2)
    {
        nx = x;
        ny = Min_Range - 1;
    }
    else
    {
        nx = x;
        ny = Max_Range + 1;
    }
    int Shape = Make_Shape(Dir);
    int Dist = Check(x, y, nx, ny, Dir, Shape);
    Time = Time + Dist;
 
    cout << Time << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}