[BOJ] 백준 3190. 뱀

▶문제설명

[BOJ] 3190. 뱀

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

▶Hint

---

 뱀이 사과를 먹었을 경우 꼬리가 길어져서 꼬리 끝의 좌표를 그대로 두면 되지만, 사과를 먹지 못 했을 경우 꼬리 끝의 좌표가 머리를 따라서 한 칸 이동해야한다.

 사과를 먹지 못했을 경우를 잘 처리해 주는 게 관건이다.

 이차원 배열 map을 만들고, 시간의 흐름에 따라서 1부터 시작해 1씩 증가된 값을 저장하여 뱀을 나타내도록 구현했다.

그리고 꼬리 끝의 좌표와 머리의 좌표를 따로 저장하여 활용했다.

사과를 먹지 못했을 경우 꼬리 끝의 좌표에서 상/하/좌/우를 탐색해 가장 큰 값을 찾고 그 값의 위치로 꼬리의 끝이 이동하도록 구현하면 사과를 먹지 못했을 경우를 적절히 처리할 수 있다.

(더 간단한 방법으로 뱀이 위치한 좌표들을 queue에 저장해서 관리하는 방법이 있다. 뱀 머리가 이동하는 좌표를 queue에 push하면서 뱀이 위치한 좌표들을 저장한다. 이렇게 하면 front에 있는 좌표가 항상 뱀의 꼬리 끝을 가리키는 좌표 값이 된다. 즉, 뱀이 사과를 먹지 못했을 경우 front에 있는 좌표 값을 pop 하기만 하면 된다.)

 방향 전환 처리는 상(0)/우(1)/하(2)/좌(3) 순으로 방향에 따라 더해줄 좌표 값을 관리하면 편하다.

오른쪽으로 90도 전환은 (dir + 1) % 4

왼쪽으로 90도 전환은 (dir + 3) % 4

dir이 2(하)인 경우 해당 식을 거치면

현재 진행방향 기준으로

오른쪽으로 90도 전환된 방향은 3(좌)

왼쪽으로 90도 전환된 방향은 1(우)이 된다.

▶Solution