백준 3190번 뱀 C++

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

 

뱀이 이동할 때마다 위치를 큐에 넣고, 보드의 정보를 갱신해준다. 만약 이동한 위치에 사과가 없다면 몸의 크기는 그대로 유지해야 하기 때문에 pop을 해주고 pop한 위치를 아무것도 없는 칸으로 바꿔준다.

사과가 있다면 몸의 크기가 늘어나기 때문에 pop을 하지 않고 진행하면 된다.

 

그리고 회전 정보를 이용하여 뱀을 회전시키고, 다음 위치가 자신의 몸이거나 벽이면 반복문을 종료한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, k, l;
vector<vector<int>> board(101, vector<int>(101, 0));
vector<pair<int, char>> rotates;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int r, c;
		cin >> r >> c;
		board[r][c] = 2;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		int cnt;
		char rot;
		cin >> cnt >> rot;
		rotates.push_back({ cnt,rot });
	}
	int row = 1;
	int col = 1;
	queue<pair<int, int>> q;
	board[1][1] = 1;
	q.push({ 1,1 });
	int dir = 1;
	int cnt = 0;
	int rotIdx = 0;
	while (true) {
		cnt++;
		int nextRow = row + dRow[dir];
		int nextCol = col + dCol[dir];
		if (nextRow<1 || nextRow>n) break;
		if (nextCol<1 || nextCol>n) break;
		if (board[nextRow][nextCol] == 1) break;
		if (board[nextRow][nextCol] == 0) {
			auto back = q.front();
			q.pop();
			board[back.first][back.second] = 0;
		}
		board[nextRow][nextCol] = 1;
		q.push({ nextRow,nextCol });
		row = nextRow;
		col = nextCol;
		if (rotIdx<rotates.size() && cnt == rotates[rotIdx].first) {
			if (rotates[rotIdx].second == 'D') {
				dir = (dir + 1) % 4;
			}
			else {
				dir = (dir + 3) % 4;
			}
			rotIdx++;
		}
	}
	cout << cnt;
};