[백준/자바] 10875 뱀

사진 클릭시 문제로 이동

---

문제

가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다.

이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다.

격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다.

이 격자판의 (0, 0) 칸에 한 마리의 뱀이 자리를 잡고 있다.

처음에는 뱀의 크기가 격자판의 한 칸의 크기와 같으며, 뱀의 머리는 격자판의 오른쪽을 바라보고 있다.

이 뱀은 자신이 바라보고 있는 방향으로 1초에 한 칸씩 몸을 늘려나가며, 뱀의 머리는 그 방향의 칸으로 옮겨가게 된다.

예를 들어 위의 그림과 같이 L = 3인 경우를 생각해 보자. 뱀은 처음에 (0, 0)에 있으며, 그 크기는 격자판 한 칸 만큼이고, 뱀의 머리가 바라보고 있는 방향은 오른쪽이다.

1초가 지나고 나면 이 뱀은 몸을 한 칸 늘려서 (0, 0)과 (1, 0)의 두 칸을 차지하게 되며, 이때 (1, 0) 칸에 뱀의 머리가 놓이게 된다.

1초가 더 지나고 나면 (0, 0), (1, 0), (2, 0)의 세 칸을 차지하게 되고, 뱀의 머리는 (2, 0)에 놓이게 된다.

이 뱀은 자신의 머리가 향하고 있는 방향을 일정한 규칙에 따라 시계방향, 혹은 반시계방향으로 90도 회전한다.

1번째 회전은 뱀이 출발한지 t1 초 후에 일어나며 i(i > 1)번째 회전은 i − 1번째 회전이 끝난 뒤 ti 초 후에 일어난다.

단, 뱀은 ti 칸 만큼 몸을 늘린 후에 머리를 회전하며 머리를 회전하는 데에는 시간이 소요되지 않는다고 가정한다.

만일 뱀의 머리가 격자판 밖으로 나가게 되면, 혹은 뱀의 머리가 자신의 몸에 부딪히게 되면 이 뱀은 그 즉시 숨을 거두며 뱀은 숨을 거두기 직전까지 몸을 계속 늘려나간다.

뱀이 머리를 회전하는 규칙, 즉 ti 와 그 방향에 대한 정보가 주어졌을 때, 뱀이 출발한지 몇 초 뒤에 숨을 거두는지를 알아내는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 L(1 ≤ L ≤ 108)이 주어진다.

두 번째 줄에는 머리의 방향을 몇 번 회전할 것인지를 나타내는 정수 N(0 ≤ N ≤ 103)이 주어진다.

다음 N 개의 줄에 뱀이 머리를 어떻게 회전하는지에 대한 정보가 주어진다.

i(1 ≤ i ≤ N)번째 줄에 정수 ti(1 ≤ ti ≤ 2 · 108)와 diri 가 차례로 주어지며 diri 는 문자 L, 또는 R 중 하나이다.

뱀은 i = 1인 경우 출발, 그 외의 경우엔 i − 1번째 회전으로부터 ti 초 후에 diri 의 방향으로 머리를 회전하며, 만일 diri 가 L 이라면 왼쪽 (반시계방향)으로, R 이라면 오른쪽 (시계방향)으로 90도 회전한다.

출력

첫 번째 줄에 답을 나타내는 값을 하나 출력한다.

이 값은 뱀이 출발한지 몇 초 후에 숨을 거두는지를 나타낸다.

예제 입력 1 

3
4
2 L
2 L
1 L
5 R

예제 출력 1 

7

예제 입력 2 

3
3
2 L
4 L
4 R

예제 출력 2 

6

힌트

첫 번째 예제의 경우 출발 후 7초가 지나고 나면 뱀의 머리가 자신의 몸 (1, 0)에 부딪히게 되고, 이때 뱀은 숨을 거둔다.

---

설명

각 2*L+1크기의 2차원 배열을 만들고 한칸씩 전진해서 코드를 구현했더니 메모리 초과가 발생했다.

L이 1억인 조건을 무시하고 문제를 풀어서 그런 결과가 발생했다.

 

L이 아닌 N을 가지고 문제를 해결해야 한다.

해당 문제는 한칸 한칸으로 문제를 해결하지 않고 선분으로 문제를 해결해야 한다.

또 헷갈렸던 부분은 평소에 행을 x, 열을 y로 놓고 풀었는데 해당 문제는 실제 좌표계처럼 행은 y, 열은 x로 생각해야 한다. 또한 실제 좌표계처럼 기존 배열과는 달리 우측으로 갈수록 x값이 커지고 위로 갈수록 y값이 커진다.

(x1, y1)과 (x2, y2)를 입력 받으면 선분을 알 수 있다고 생각해보자.

L이라는 값을 입력받았을 때 뱀의 머리가 격자판에 닿은지 여부를 판단하기 위해 아래 네개의 점을 이용하면 아래 그림처럼 격자판 테두리에 파란 직선이 4개가 생긴다.

• (-L-1, L+1)
• (L+1, L+1)
• (L+1, -L-1)
• (-L-1, -L-1)

선분을 보면 수평선과 수직선 밖에 없다는 사실을 알 수 있다.

오른쪽, 아래쪽, 왼쪽, 위쪽 방향으로 움직일 수 있고 수평선과 수직선이 있다면 총 8개의 경우에 대해 생각해 보면 된다.

각 경우에 대해 부딪치는 최소의 거리를 생각해봐야 한다.

 

2초후에 방향을 바꾸는데 모든 선분을 살펴봐도 현재 위치에서 부딪치려면 가장 최소의 거리가 3이라면 안 부딪치고 방향을 회전할 것이고 1이라면 부딪치고 더이상 진행할 수없을 것이다.

 

수평선인 경우

    오른쪽의 경우 cy == y1 == y2가 모두 같고 부딪치기 위해서는 cx < x1이여야 한다. 

if (cy == al.get(j).y1 && cx < al.get(j).x1) {
	t = Math.min(t, al.get(j).x1 - cx);
}

    아래쪽

if (al.get(j).x1 <= cx && cx <= al.get(j).x2  && al.get(j).y1 < cy) { 
	t = Math.min(t, cy - al.get(j).y1);
}

    왼쪽

if (cy == al.get(j).y1 && al.get(j).x2 < cx) {
	t = Math.min(t, cx - al.get(j).x2);
}

    위쪽

if (al.get(j).x1 <= cx && cx <= al.get(j).x2  && cy < al.get(j).y1) { 
	t = Math.min(t, al.get(j).y1 - cy);
}

수직선인 경우

    오른쪽

if (al.get(j).y1 <= cy && cy <= al.get(j).y2  && cx < al.get(j).x1) { 
	t = Math.min(t, al.get(j).x1 - cx);
}

    아래쪽

if (cx == al.get(j).x1 && al.get(j).y2 < cy) {
	t = Math.min(t, cy - al.get(j).y2);
}

    왼쪽

if (al.get(j).y1 <= cy && cy <= al.get(j).y2 && al.get(j).x1 < cx) { 
	t = Math.min(t, cx - al.get(j).x1);
}

    위쪽

if (cx == al.get(j).x1 && cy < al.get(j).y1) {
	t = Math.min(t, al.get(j).y1 - cy);
}

n번의 회전을 돌고 마지막으로 1번 더 뱀은 움직인다.

마지막 회전을 마치고나서 뱀은 더이상 방향을 바꾸지 않고 움직이다 부딪치기 때문에 부딪칠 수 밖에 없는 거리를 주고 t만큼 움직인 값만 결과에 더해준다. 

코드