백준 3190번 뱀

domybest·2021년 4월 13일
0

백준

목록 보기
25/36
post-thumbnail

문재
풀이 코드

알고리즘

풀이 시간 40분을 목표로 하라고 하였지만 70분이 걸려서 풀었다. 구현 아이디어 자체는 괜찮았지만 역시 반복문에서의 자잘한 구현 미스가 있어서 시간이 오래 걸린 것 같다.
먼저 뱀이 보드 위를 '특정 방향으로 돌아다닌다' 라고 했으므로 바로 dx, dy 배열을 떠올려야 할 것이다. 첫 방향은 오른쪽 이므로 행은 0, 열은 +1 되는 방향으로 움직이게 될 것이다. 이에 착안해 dx, dy 방향 배열을 생성한다.

  1. 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시키는 기능
  2. 이동한 칸에 사과가 있을 때
  3. 이동한 칸에 사과가 없을 때, 꼬리를 삭제 시키는 기능
  4. 이동했는데 벽에 부딪혔을 때 즉, 인덱스를 초과 했을 때
  5. 이동했는데 자신의 몸이 있을 때 기능
구현해야 할 부분은 이렇게 총 5가지 정도로 생각하면 된다. 1번은 어떻게 할까? dx, dy 방향 배열에 따라 인덱스를 더하여 머리를 다음 칸에 위치시키고 이 '위치시켰다'를 표현하기 위해 그 곳의 map 원소 값을 1로 만든다.

<map 배열의 규칙>

  1. 사과가 있는 곳은 5로 하겠다.
  2. 뱀이 존재하는 곳은 전부 1로 하겠다.
  3. 시작 당시 (1,1)은 뱀이 있으므로 1이다.
  4. 아무것도 존재하지 않는 곳은 0이다.
나만의 map 배열 규칙을 만들고 시작해야 한다. 이 후에 구현을 진행한다. 이제 2번 사과가 있을 때 즉 map의 원소값이 5일 때이다. 그러면 그냥 이동한 칸의 원소값을 1로 만들고 다음 반복으로 넘어가면 된다. 
사과가 없을 때는 꼬리를 삭제, 즉 꼬리의 index에 해당하는 map 원소값을 0으로 만들어야 한다.여기서 문제는 꼬리가 삭제되면 다음 꼬리는 어디가 될 것이냐이다. 그래서 이동할 때마다 '예비 꼬리'들을 저장해 놓아야한다. 먼저 저장한 예비 꼬리를 먼저 사용해야 하므로 선입선출 구조의 Queue 자료구조에 저장하겠다. 그래서 사과가 없는 곳에 가면 queue에서 꼬리 하나를 삭제하고 그 index의 map 원소값을 0으로 만든다.
벽에 부딪혔을 때는 index를 벗어난 경우를 예외 처리 해 주면 된다.
마지막으로 몸에 부딪힐 때라 하면 map 원소가 1인 곳을 만난다는 말과 같다. 

> 역시 하라는 대로만 하면 아이디어 자체는 어렵지 않은 문제였다. 예비 꼬리를 큐 자료구조에 저장하는 것을 금방 떠올릴 수 있고 반복문에서 자잘한 실수만 하지 않았다면 시간이 70분이나 걸리지 않았을 것이다.. 더 연습하자!
profile
기억할 때 까지 반복!

0개의 댓글