https://www.acmicpc.net/problem/3190
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따
www.acmicpc.net
백준 3190 뱀
시뮬레이션 문제로, 문제를 잘 파악하는 것이 중요하다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
=> 여기서 큐를 쓰면 위의 규칙을 쉽게 구현할 수 있음. 먼저 다음칸에 위치할 때, 큐에 현재 위치를 넣고
사과가 없을 경우에는 큐에서 poll로 빼준다..
나머지 부분은 주어진 조건대로 뱀의 방향을 하면서, 몸에 닿는 지 보드의 끝으로 가는 지 확인해주면 된다.
'알고리즘' 카테고리의 다른 글
| 백준 14502 연구소 - JAVA (0) | 2020.03.02 |
|---|---|
| [백준 13458 - JAVA] 시험감독 (0) | 2020.03.01 |
| [JAVA 백준 16236] - 아기상어 (0) | 2020.02.27 |
| [삼성 SW 역량 테스트 기출 문제집] 백준 17144 미세먼지 안녕! (0) | 2020.02.25 |
| [삼성 SW 역량 테스트 기출 문제집] 백준 14503 - 로봇청소기 (0) | 2020.02.24 |