백준[3190] 뱀

아이디어

• [시뮬레이션]을 구현할 줄 안다
• [큐]를 사용할 줄 안다

접근방식

1. 뱀의 몸통의 처음과 끝을 저장해주기 위해 queue를 사용한다
2. 배열을 만들어 시간마다 배열을 채크하여, D 혹은 L일 경우 방향 회전을 한다
3. while문을 이용하여 다음 뱀 머리의 위치를 저장하되, 보드의 크기를 넘으면 break 한다
4. 사과가 있으면 사과만 제거해준다
5. 사과가 없으면 꼬리가 없어지되, 머리가 마지막 꼬리에 부딪힐 경우 break 해주고, 그게 아니라면 꼬리 부분을 false 해주고 queue를 pop해준다
6. 몸통의 위치를 조사하여, 다음 뱀 머리 위치가 몸통과 부딪힐 경우 break 해주고, 그게 아니라면 다음 뱀 머리 위치를 true로 표시해준다

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>

using namespace std;

//사과의 위치 1이면 사과가 존재
int board[101][101];

//뱀 몸통이 있는가?
bool Is_There_Snake[101][101];

//방향 저장
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

// i 시간에 방향전환을 함 
char swift[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int board_Size,Apple_Cnt; cin >> board_Size >> Apple_Cnt;

	for (int i = 0; i < Apple_Cnt; i++)
	{
		int col, row; cin >> col >> row;
		board[col][row] = 1;
	}

	int swift_Cnt; cin >> swift_Cnt;

	for (int i = 0; i < swift_Cnt; i++)
	{
		int swift_Time;
		char Direction;
		cin >> swift_Time >> Direction;
		swift[swift_Time] = Direction;
	}

	//뱀의 몸통이 어디에 위치하고 있는가
	queue<pair<int,int>> snake;

	//처음위치 초기화
	snake.push({ 1,1 });
	Is_There_Snake[1][1] = true;

	//시간
	int answer_Time = 0;

	//지금 방향
	int now_Direction = 0;

	while (1)
	{
		answer_Time++;

		int next_col = snake.back().first + dy[now_Direction];
		int next_row = snake.back().second + dx[now_Direction];

		//벽을 부딪히면 종료
		if (next_col < 1 || next_col > board_Size || next_row < 1 || next_row > board_Size) break;

		snake.push({ next_col,next_row });

		//방향 변경
		if (swift[answer_Time] == 'D')
		{
			now_Direction += 1;
			if (now_Direction == 4) now_Direction = 0;
		}

		else if (swift[answer_Time] == 'L')
		{
			now_Direction -= 1;
			if (now_Direction == -1) now_Direction = 3;
		}

		//사과가 있으면? 사과 없어지고 꼬리 움직이지 않음
		if (board[next_col][next_row] == 1)
		{
			board[next_col][next_row] = 0;
		}
		
		//사과가 없으면? 꼬리 없어짐
		else
		{
			if (Is_There_Snake[next_col][next_row] == true) break;
			Is_There_Snake[snake.front().first][snake.front().second] = false;
			snake.pop();
		}

		//만약 원래 몸통이 있었다면? break
		if (Is_There_Snake[next_col][next_row] == true) break;

		else Is_There_Snake[next_col][next_row] = true;
	
	}

	cout << answer_Time << endl;

	return 0;
}

평가

시뮬레이션을 구현할 줄 아는가를 물어보는 문제.
저는 시뮬레이션이 익숙하지 않아 약 30분정도 고민을 했습니다. 뱀 몸통의 위치를 고려해야 한다는 점에서, queue를 사용하였고, queue를 일일히 조사하기가 어려우니 배열을 따로 만들어 몸통 위치의 여부를 true, false로 표기하였습니다.
또한, dy, dx 방향전환을 할 때, dy의 값이 -1 인지 1인지를 정확히 파악하지 않아 틀린 점을 찾는데 애를 많이 먹었습니다.

• 배울 것
  1) 배열의 dy, dx 값과, 설정한 dy, dx 값이 같은 건지 확인 하자