[백준 3190] 뱀

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

풀이

하루에 삼성 기출문제 하나푸는것도 벅차는것같네요.. 하루에 4개 5개씩 푸는분들 진짜...말도안돼 

문제를 제대로 이해하고 풀어보려면 일단 첫번째 test 케이스를 직접 그려보면됩니다.

그려보면 느낄 수 있는 것

1. 방향회전 연산의 시간은 누적되고, X초 전에 벽부딪히거나 자기몸 일부 만나면 종료

ex) 3 'D'  -> 15 'L'   => 3초일때 연산 후 12초 후 15초 일 때 계산

2. 방향 꺾을 때 머리제외한 몸통+꼬리 부분이 벽이 부딪히는걸 어떻게 해결할까?

좌표상에서 방향을 꺾고나서의 뱀의 모양 표현 불가능

-----> 지나갈 때 마다 좌표에 뱀의 흔적을 남기자.

3. 몸의 길이가커지고(사과발견 시) 좌표를 한칸 앞으로 당기는 연산(빈칸 발견시)을 어떻게 처리할까?

꼬리를 삭제하고, 머리를 추가한다(길어진다)? -> 앞 뒤로 삽입삭제 가능한 덱 떠올림

------> 덱에 뱀의 이동경로를 표현하자(요소의 갯수=뱀의 길이가 되게끔)

결론

1. 뱀을 나타내기위해 덱을 사용한다. (머리=front, 꼬리=back)

2. 꼬리를 자를 때(빈칸발견)는 back을 pop시킨다.(꼬리이므로) 

3. 길이가 길어질때는(사과발견) front에 머리좌표를 넣어주자.

4. 뱀이 지나간 좌표를 맵에 표현(2) 하고, 없는 좌표는(꼬리가 짤린 좌표포함) 0으로 표현하자.

5. 뱀이 지나갈 때 값이 2인좌표를 만나면 종료시키자.

코드

#include<iostream>
#include<deque>
#include<vector>
using namespace std;
//꼬리는 0, 머리는 2 


//뱀의위치는 좌표상에2로표시
//뱀의위치가 바뀔떄마다 그 위치를 덱front에삽입
//사실상 덱back의 좌표는 꼬리부분 

//사과 자리 1, 빈자리0
//뱀좌표: 2



//동북서남
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };
int map[101][101];
vector<pair<int, char>>v;
deque<pair<int, int>>dq;
void func();
int n, time;
int main()
{
	int k, y, x, l,num;
	char c;
	//방향연산의 횟수 
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
	{
		cin >> y >> x;
		map[y][x] = 1;
	}
	cin >> l;
	for (int i = 1; i <= l; i++)
	{
		cin >> num >> c;
		v.push_back(make_pair(num, c));
	}
	
	func();
	cout << time << endl;
}
void func()
{
	//cnt= 연산의 갯수
	int y =1, x = 1, go = 0, cnt=0;
	dq.push_back({ y,x });
	map[y][x] = 2;
	while (1)
	{
		time++;
		int nx = x + dx[go];
		int ny = y + dy[go];
		//벽이나, 자신의 몸의일부만나면 끝
		if (nx<1 || ny<1 || nx>n || ny>n || map[ny][nx] == 2)
			return;

		else if (map[ny][nx] == 0)
		{
			//뱀이 지나감
			map[ny][nx] = 2;
			//꼬리부분이 2로 칠해져있음(지나갔기때문에)
			//0으로 처리해주고 덱에서도 꼬리부분 짜름
			map[dq.back().first][dq.back().second] = 0;
			//덱의 마지막원소(좌표)가 꼬리끝부분(좌표)이므로 짤라버림
			dq.pop_back();
			//머리부분을 front에삽입 : back아님!!
			dq.push_front({ ny,nx });
		}
		else if (map[ny][nx] == 1)
		{
			map[ny][nx] = 2;
			//마찬가지로 front에 삽입 : back아님!!
			dq.push_front({ ny,nx });
		}
		
		if (cnt < v.size()) {
			//연산 횟수에대해 방향갱신
			if (time == v[cnt].first)
			{
				if (v[cnt].second == 'L')go = (go + 1) % 4;
				else if (v[cnt].second == 'D')go = (go + 3) % 4;
				cnt++;
			}
		}
		y = ny;
		x = nx;
	}
}

결과