[BOJ] 백준 10875번: 뱀

뱀

문제

(0, 0) 에서 뱀이 오른쪽 방향을 보고 출발한다. n개의 명령 (이전 명령으로 부터 t시간 뒤에, dir 방향으로 머리를 돌림)을 수행하면서 격자판 밖으로 나가거나 자신의 몸에 부딪히는 시간을 구하는 문제이다.

문제 풀이

뱀이 지나온 칸들을 선분으로 저장해서 관리하기로 한다.

1. 초기에 테두리 선분 4개를 추가해준다.

2. 추가적으로 모든 명령이 끝난후 에도 선분에 부딪히지 않을수 도 있으므로 (inf,R) 명령을 하나 넣어준다.

3. 현재 (x,y)에서 dir 방향으로 이동할 때 현재 까지 저장된 선분들과 비교하여 최대로 이동할 수 있는 시간을 구한다.

4. 이 시간이 t보다 같거나 작으면 t시간을 이동하기 전에 선분들 중 하나에 부딪히는 것이므로 답을 출력한다.

5. 아니라면 t시간 만큼 이동한 후에 dir을 회전한다. 

6. 현재 이동한 선분을 추가한다.

7. [3,6] 을 모든 명령에 대해서 반복한다.

8. 선분은 최대 n개 만큼 추가 생성될 수 있고, 명령은 n개 있으므로 \(O(N^2)\)에 해결 가능하다.

 

소스 코드