백준 3190 뱀

문제링크

코드 설명

백준의 삼성 기출 복원 문제집 문제이다.
구현력이 좀 약하다 생각하여 연습겸 풀어보았다.
꼬리부분을 빼는것을 고민하다가 Deque를 생각하였다.
뱀과같은 문제일때 유용한 stl인거 같아 기억해놔야 할것같다.

삼성의 구현문제경우 dx[],dy[]를 이용한 방향성문제가 많은것같다.

생각해야할 case
1. 머리가 지나가면서 map[ny][nx]=2;
2. 사과가있는부분은 map[y][x]=1로 설정
3. 사과를 만날때와 아닐때 구별해서 map저장
4. 자기몸을 다시만날때(map[ny][nx]==2) or 벗어날때 break;

소스 코드

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
struct baam {
	int len;
	int hy, hx;
	int ty, tx;
};
int dir[4] = { 1,2,3,4 }; //1:오 2:아래 3: 왼 4: 위
baam bam;

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int N;
int L; //방향변환횟수
int K;//사과개수
int map[101][101];
bool visited[101][101];

queue<pair<int, char> > arr;
int cnt;
int Turn(int dir, char abc) {

	if (abc == 'L') {
		if (dir == 0) return 3;
		if (dir == 1) return 0;
		if (dir == 2) return 1;
		if (dir == 3) return 2;
	}
	else if (abc == 'D') {

		if (dir == 0) return 1;
		if (dir == 1) return 2;
		if (dir == 2) return 3;
		if (dir == 3) return 0;
	}
}
void move() {
	int dir = 0;
	deque<pair<int, int>> q;
	int y = 0;
	int x = 0;
	q.push_back({ y,x });


	while (1) {
		cnt++;
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx] == 2) {
			if (cnt != 1) break;
			
		}
		else if (map[ny][nx] == 0) {
			map[ny][nx] = 2;
			map[q.back().first][q.back().second] = 0;
			q.push_front({ ny,nx });
			q.pop_back();
			

		}
		else if (map[ny][nx] == 1) {
			map[ny][nx] = 2;
			q.push_front({ ny,nx });
		}

		if (!arr.empty()) {
			if (cnt == arr.front().first) {
				if (arr.front().second == 'L') {
					dir = Turn(dir, 'L');
				}

				else if (arr.front().second == 'D') {
					dir = Turn(dir, 'D');
				}
				arr.pop();
			}
		}
		x = nx;
		y = ny;
	}
}
int main() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a;
		cin >> a;
		int b;
		cin >> b;
		b = b - 1;
		a = a - 1;
		map[a][b] = 1;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		int a;
		char b;
		cin >> a >> b;
		arr.push({ a,b });
		
	}
	move();

	cout << cnt;

	return 0;
}