[백준 / BOJ] 3190 뱀

문제

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

3190번: 뱀

N*N보드에서 뱀이 이동한다. 이때,

먼저 뱀의 머리를 움직인다.

뱀의 머리가 도착한 위치에 사과가 있다면, 꼬리는 그대로 있고 머리만 움직인다.(뱀의 몸의 길이가 한칸 늘어남)

아니라면, 몸의 길이를 줄여 꼬리가 위치한 칸을 비워준다.

풀이

처음에 문제 조건을 잘 읽지 않고 풀어서 힘들었다.

먼저 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다. <- 이 조건을 내 맘대로 머리와 꼬리를 동시에 움직인후, 사과가 있다면, 꼬리를 늘려주는식으로 구현했었다;;

 

자기몸과 부딪히면 종료해주기위해, 뱀의 모든 위치를 알아야하는데, 뱀의몸을 표현해주기위해서, 앞뒤 참조가 자유로운 deque과 check[][]배열을 통해 구현해줬다.

ex) check[2][5] = 1; // Y = 2 X = 5위치에 뱀의 몸이 존재함

deque은 뱀의 머리와 꼬리를 늘리고 줄이기 위해 선언한다.

예를들어, deque에 {1,1} {1,2} {1,3} 이 저장되어있다면, 뱀의 머리는 1,3 꼬리는 1,1에 있는것이다. 

만약, 뱀의 머리를 (1,4)위치로 움직였는데 사과가 존재한다면, deque 에는 {1,1} {1,2} {1,3} {1,4}가 존재할것이다. (반대라면, {1,1}이 사라진다.)

 

먼저 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다

위 조건만 주의하며 풀면된다.

 

소스코드

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

devxb/JJUNalgo