[백준 / BOJ] 10875 뱀

문제

출처 : www.acmicpc.net/problem/10875

10875번: 뱀

2차원 그리드에서 뱀이 움직인다.

뱀은 1초가 지날때마다, 바라보는 방향으로 한 칸씩 몸의 길이를 늘려가며 움직인다. 

뱀은 자신의 몸과 닿거나 2차원 그리드 범위 밖으로 나가면 몸을 늘리며 숨을 거둔다. 

뱀이 머리를 회전하는 시간과 방향이 주어질때, 뱀이 언제 숨을 거두는지 출력하는 문제다.

 

풀이

시뮬레이션 문제다.

 

문제의 조건을 읽어보면, 그리드의 길이가 가로 세로 각각 최대 4억까지 증가할수있기때문에, 행렬로 뱀의 몸이 있는 위치(뱀이 지나간위치)를 표현할수없다.

뱀이 최대로 움직일경우 200000000^2만큼의 원소가 생성되기 때문에, 동적배열또한 뱀의 위치를 표현할수없으며, 한칸 한칸 움직일경우 시간초과가 나오게된다.

 

뱀은 항상 자신이 바라보고있는 방향을 향해 직선으로 움직인다는 점을 이용하면 뱀의 다음위치를 상수시간에 구해줄수 있다.

 

시뮬레이션이 끝나는 기저 조건(뱀이 숨을 거두는 조건)을 구현하는게 어려웠는데, 아이디어는 다음과 같다.

 

1. 뱀이 자신의 몸과 만난다.

- 뱀은 항상 직선으로만 움직이므로 뱀이 과거에 지나갔던 직선들의 시작점과 끝점만 알고있다면 직선이 교차하는지 판별해줄수있다. 

예를들어, 현재 위치를 (posX, posY) 현재위치에서 이동해야할 다음위치를 (nextX, nextY) 라고하자. 이때, 뱀이 이동하면서 그릴 선분은 시작점이 (posX, posY) 끝점이 (nextX, nextY)가 된다. 뱀이 과거에 지났던 경로또한 하나의 선분이기때문에, 과거에 만들었던 선분들과 현재 만드는 선분을 비교해가며 교차하는지 확인하면 된다.

예제 1의 경우 뱀이 만드는 선분은 순서대로 다음과 같다.

vector<pair<pair<int,int>,pair<int,int> > > vec; // {{posX,posY},{nextX,nextY}} 일때,

vec = [

{{0,0},{2,0}}

{{2,0},{2,2}}

{{2,2},{1,2}}

]

(마지막 {{1,2},{1,0}}의 경우 뱀이 숨을 거뒀기 때문에 안만들어도 상관없다.)

 

만들어지는 선분의 갯수는 총 N개 이며, 한번 탐색마다 N번 반복하므로 시간복잡도는 O(N^2)이다.

 

2. 뱀이 그리드 밖으로 나간다.

- 뱀의 머리가 그리드 범위 밖으로 나가는지 확인해주면된다.

 

위 기저조건을 구현하면 풀린다.

주석을 지우지 않고 소스코드를 올리니 자세한 구현은 아래 소스코드를 참고하도록 하자.

 

풀면서 주의할점이 

1. 뱀이 한바퀴를 돌아서 원점(0, 0)으로 돌아올경우 

2. 뱀이 최대로 움직일경우 int범위를 벗어날수있으므로 long long으로 선언해서 풀어야한다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10875%20%EB%B1%80/main.cpp

devxb/JJUNalgo