백준 - 3190번 뱀

문제

상하좌우로 움직이는 뱀 게임
사과를 먹으면 몸의 길이가 늘어난다
벽이나 자기 자신 몸과 부딪히면 게임이 끝난다

보드의 크기, 사과의 위치, 뱀의 방향 전환 정보가 주어질 때
게임이 끝나는 시간을 구해라

생각

문제 분류는 큐로 되어있긴 하고,
뱀이 앞으로 늘어났다 뒤에가 줄었다 하니까 많은 사람들이 덱을 써서 풀긴하던데

나는 자기 자신과 부딫혔는지 검사할 때 큐의 모든 곳을 봐야한다는게
큐를 사용하는 이유(맨 앞, 맨 뒤만 값 보고, 빼고, 넣고 할 수 있음)랑 안 맞는다고 생각해서

맵에 뱀 자체를 표현하고(부딫힌 여부 검사하기 용이),
머리와 꼬리 위치를 가지고 다니기로 했다

머리는 앞으로 어디로 가야 할지 알도록 현재 머리가 바라보는 방향을 저장해놨고,
꼬리는 줄어든다면 어느 방향으로 줄어들어야 할지 알도록
머리가 어느 방향으로 이 위치를 지나갔는지 저장을 해놨다
그럼 꼬리는 아 머리가 다음에 지나간 방향으로 줄어들면 되겠구나! 아니까!!

그래서 map은 다음과 같은 수들을 저장해놓는다
0(아무 것도 없음)
1~4(방향 벡터 index + 1)
40(사과)

상세한 구현만 잘해주면 쉽게 풀 수 있다

• 맵은 1,1 부터 시작하는데
  나는 0,0 을 생각하고 문제를 풀어서
  입력 받을 때 -1 인덱스에 값을 저장해줬다

• 아웃 오브 바운드 문제가 나길래
  map에 정보 저장을 잘 못 한건가, 뭔가 잘 못 짜졌나,, 하고 이것저것 둘러보다가
  모든 방향 전환 정보를 다 사용했을 때 더 볼게 없어서 터진거였다
  (이거에 시간 좀 쓴 듯..)

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n, k, l;
int map[105][105]; // 1~4 d[i]로 지나감, 40 사과
vector<pair<int, char>> info;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int tx, ty;
		cin >> tx >> ty;
		map[tx-1][ty-1] = 40;
	}

	cin >> l;

	for (int i = 0; i < l; i++) {
		int tt;
		char tc;
		cin >> tt >> tc;
		info.push_back(make_pair(tt, tc));
	}

	int t = 0, i = 0; //현재 소요 시간, 사용한 info 수
	int nowd = 2, nextx = 0, nexty = 0; //현재 방향, 다음 머리 위치
	int nexttx = 0, nextty = 0; //다음 꼬리 위치

	while (true) {
		if (i < l) { //모든 방향 전환 정보를 다 사용했을 때는 안 보도록 처리
			if (t == info[i].first) {
				if (info[i].second == 'D') {
					nowd--;
					if (nowd == 0) {
						nowd = 4;
					}
				}
				else {
					nowd++;
					if (nowd == 5) {
						nowd = 1;
					}
				}
				i++;
			}
		}
		
		map[nextx][nexty] = nowd;
		nextx += dx[nowd - 1];
		nexty += dy[nowd - 1];
		t++;

		if (nextx >= n || nexty >= n || nextx < 0 || nexty < 0) {
			break;
		}
		
		if (map[nextx][nexty] != 0) {
			if (map[nextx][nexty] == 40) {

			}
			else {
				break;
			}
		}
		else {
			int tempd = map[nexttx][nextty];
			map[nexttx][nextty] = 0;
			nexttx += dx[tempd - 1];
			nextty += dy[tempd - 1];
		}
	}
	cout << t;
	
	return 0;
}