[백준] 3190 뱀

들어가기

• 3190 뱀 문제는 자료구조 문제입니다.
• Deque를 활용하면 쉽게 풀 수 있는 문제입니다.
• 문제에서 제시한 조건대로 시뮬레이션을 진행하면 됩니다.

문제

• N은 뱀 문제의 N X N 격자판 크기를 나타냅니다.
• K는 사과의 개수를 나타내며 격자판에 사과를 표시해둡니다.
• L은 게임 시작 후 X 초 이후에 뱀의 방향을 변환할 정보 개수입니다. 
  • 뱀의 방향은 'L' , 'D'의 정보로 변환합니다.
  • 'L' 일 경우 90도 반시계 방향
  • 'D' 일 경우 90도 시계 방향

풀이

• 먼저 뱀이 움직이는 방향을 정리합니다.

• 위와 같이 뱀이 움직일 방향의 index를 두면 'L' / 'D'를 아래와 같이 표현할 수 있습니다.
  • L = 현재 방향 - 1
  • D = 현재 방향 + 1

• 뱀 게임에서는 뱀의 머리와 꼬리의 위치를 추적하는 것이 중요합니다. 
• 이때 Deque를 활용하면 뱀의 머리 / 몸통 / 꼬리를 쉽게 추적할 수 있습니다.

• 뱀의 머리의 역할은 2가지입니다.
  • 매 초마다 앞으로 이동하면서 deque의 제일 앞에 다음 위치를 저장합니다.
  • 그럼 이전의 머리는 자연스럽게 몸통이 됩니다.
  • 그리고 격자판에 뱀의 위치를 표시합니다. (뱀의 머리가 이동했는데 몸통에 부딪친 경우 게임을 종료하기 위해)
• 뱀의 꼬리의 역할은 2가지입니다.
  • 매 초마다 뱀의 머리가 앞으로 이동했을 때 이동한 격자판에 사과가 없으면 deque의 제일 마지막을 제거합니다.
  • 사과가 없으면 격자판에서 꼬리의 위치를 지웁니다.
• 그런 다음 매초마다 아래 그림과 같은 작업을 진행하면 됩니다.
• 문제에서 최대 진행하는 초는 10,000초이므로 시간 초과가 발생할 일은 없습니다.

소스보기