알고리즘/삼성SW역량테스트기출
-
[백준 3190번 - 뱀] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 16. 22:27
백준 3190번. N x N 정사각 보드가 있고, 초기 상태의 뱀의 위치는 (0,0), 몸길이는 1이다. (보드 한칸 = 몸길이 1) 주어진 방향대로 1초에 한 칸만큼 이동한다. 만약 그 칸에 사과가 있으면 먹고, 꼬리는 그대로 둔 채 머리만 이동한다. (즉, 몸 길이가 늘어난다.) 만약 그 칸에 사과가 없으면, 머리와 꼬리가 같이 이동한다. (즉, 몸 길이는 그대로다.) 사용한 알고리즘은 다음과 같다. deque 시뮬레이션 간략한 설명 뱀의 몸이 있는 위치를 저장하기 위해서 deque 를 하나 두었다. deque 는 앞/뒤 양방향으로 push/pop이 가능하기 때문에 뱀의 길이와 머리, 꼬리 위치가 변함에 따라 좌표 저장이 용이할 것이라는 생각이 들었다. 사과의 위치를 저장하기 위한 map, 뱀의 몸이..