BOJ: 뱀(3190) [C++]

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

 

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

 

 

벽이나 자기 몸에 안 부딪히도록 움직이는데 사과를 먹으면 길이가 늘어나고 안 먹으면 길이가 그대로라는 것

2차원 벡터를 이용한다

int solution(int n, int k, int l, vector<vector<int>>& apple, vector<int>& rot_t, vector<int>& rot_d) {
	vector<vector<int>> board(n, vector<int>(n)); //게임 보드판(nxn)
	map<int, char> cmd;
	for (int i = 0; i < k; i++) {
		board[apple[i][0] - 1][apple[i][1] - 1] = 2; //사과 표시
	}
	for (int i = 0; i < l; i++) {
		cmd[rot_t[i]] = rot_d[i];
	}
	int answer = playGame(n, board, cmd);
	return answer;
}

일단 playGame을 만들기 전에, 입력받은 것들을 필요한 형태로 바꿔주는 작업이 필요하다

n x n 보드에 사과위치를 표시하고 cmd라는 맵에 이동정보를 저장

 

뱀의 머리위치와 꼬리위치를 관리하기 위해 자료구조는 덱을 사용한다

머리는 front 꼬리는 back 그런식으로

typedef pair<int, int>ci;

int playGame(int n, vector<vector<int>>& board, map<int, char>& cmd) {
	//우 상 좌 하
	int dr[4] = { 0,-1,0,1 };
	int dc[4] = { 1, 0, -1, 0 };
	//뱀 초기화
	deque<ci>snake;
	snake.push_front(ci(0, 0));
	board[0][0] = 1;

	int t = 0, head = 0; //시간, 뱀 머리방향
	while (1) {
		t++;
		int nr = snake.front().first + dr[head];
		int nc = snake.front().second + dc[head];
		if (nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr][nc] == 1) {
			break;
		}
		if (board[nr][nc] != 2) {
			//사과가 있지 않다면 꼬리가 위치한 칸을 비워줌
			board[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}
		//다음 칸에 머리를 위치시킴
		snake.push_front(ci(nr, nc));
		board[nr][nc] = 1;

		//방향 변환 확인
		if (cmd[t] == 'L')
			head = (head + 1) % 4;
		if (cmd[t] == 'D')
			head = (head + 3) % 4;
	}
	return t;
}

처음에 오른쪽을 보고 있다고 했으니 방향을 나타내는 dr, dc도 오른쪽부터 만들어주자

시작 시 첫칸에 뱀머리가 위치할 테니 덱의 front에 (0,0)을 푸시하고 보드에도 뱀이 있다는 표시를 1로 해준다

nr, nc는 뱀머리가 위치하게 될 칸을 의미한다. 현재 머리위치인 front에 방향에 따른 증감을 적용해준 값.

종료조건은 벽에 부딪히거나(위치가 0보다 작거나 n이 됨), 자기자신에게 부딪히기(가야 하는 보드 칸이 이미 1임)이므로 저런 식으로 or로 연결해 설정해준다.

사과의 유무에 따라 동작이 달라지므로 조건문 설정이 필요하다

사과가 없다면(board[nr][nc]!=2) 길이가 늘어나서는 안 되니까 꼬리가 있던 칸을 비워준다. 보드도 비우고 뱀을 의미하는 덱에서 pop도 해줘야 하는 점을 주의

그리고 머리를 방향에 따라 한칸 옮겨주면 된다. 머리 부분이니까 push_front를 써준다. 여기서도 보드 value를 1로 바꿔줘야 함에 유의..

마지막으로 head의 방향 변환 여부를 확인해주고, 해당 key에 해당하는 value가 있다면 방향에 따라 head 방향을 재설정해준다.

 

입력받는 것이 보드가 아닌, 사과위치와 이동정보이기 때문에 적절하게 변환하는 과정이 필요했다.

사과는 k행 2열의 2차원 int 벡터로, 이동정보에서 시간은 int, 방향은 char로 받고, 그걸 다시 nxn의 2차원 벡터인 board로, <int,char>형의 map인 cmd로 바꿔주는 것..

구현 자체는 문제가 제시한 조건을 따라가면 되지만 이래저래 자잘한 부분이 많은 그런 문제