백준 알고리즘 문제 풀이 c/c++ -3190-

덱 자료구조를 사용하면 조금 더 편하게 구현할 수 있는 것 같다

문제의 요구에 따라 차례대로 구현하면 된다

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

int N; // 보드 크기
int K; // 사과 개수
int L;

int arr[110][110] = { 0, };

int Time = 0;

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

struct Info {  // 변환 시간 및 방향 정보
	int seconds;
	char dir;
};

struct Snake {  // 뱀이 가지고 있는 좌표 정보
	int dir;  // 상하좌우 = 0123
	int y;
	int x;
};

deque<Info> info;  // 변환 정보

int main() {

	scanf("%d", &N);
	scanf("%d", &K);

	for (int i = 0; i < K; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;
		b--;

		arr[a][b] = 1;  // 사과가 있는 곳은 1로 표현
	}

	scanf("%d", &L); // 변환 정보

	for (int i = 0; i < L; i++) {
		int a;
		char b;
		scanf("%d", &a);
		scanf(" %c", &b);

		Info ii = { a, b };
		info.push_back(ii);
	}

	//for (int i = 0; i < info.size(); i++) {
	//	printf("%d %c\n", info[i].seconds, info[i].dir);
	//}

	deque<Snake> snake; // 뱀 정보
	Snake init;
	init.dir = 3; // 오른쪽 방향(초기 문제에 주어짐)
	init.y = 0;
	init.x = 0;
	
	snake.push_back(init);

	bool stop = false;

	while (1) {
		Time++;  // 시간 증가
		

		int direction = snake.front().dir;  // 현재 방향

		int headY = snake.front().y;
		int headX = snake.front().x;

		//printf("%d %d %d\n", headY, headX, direction);

		int nextY = headY + dy[direction]; // 다음 갈 곳 y 좌표
		int nextX = headX + dx[direction]; // 다음 갈 곳 x 좌표

		// 벽에 닿은 경우
		if (nextY == -1 || nextY == N  || nextX == -1 || nextX == N ) {
			stop = true;
			break;
		}
		else {
			// 몸에 닿는지 체크하기
			for (int i = 0; i < snake.size(); i++) {
				if (snake[i].y == nextY && snake[i].x == nextX) {
					stop = true;
					break;
				}
			}

			if (stop == true) {
				break;
			}

			int nextDirection = direction;  // 전환 시간아니면 방향 그대로 유지

			// 벽도 아니고 몸통에 닿지도x
			// 1. 방향 전환 되는 시간인지 체크
			if (!info.empty()) {   // 시간정보 덱이 비게될 수 도 있으므로 체크 꼭 해줘야 오류 발생X !!
				if (Time == info.front().seconds) {
					char d = info.front().dir;
					if (d == 'D') {  // 오른쪽 회전
						if (direction == 0)
							nextDirection = 3;
						else if (direction == 1)
							nextDirection = 2;
						else if (direction == 2)
							nextDirection = 0;
						else
							nextDirection = 1;
					}
					else { // 왼쪽 회전
						if (direction == 0)
							nextDirection = 2;
						else if (direction == 1)
							nextDirection = 3;
						else if (direction == 2)
							nextDirection = 1;
						else
							nextDirection = 0;
					}

					info.pop_front();
				}
			}

			// 2. 사과가 있는지 체크
			// 먼저 머리 하나 추가
			Snake newHead;
			newHead.dir = nextDirection;
			newHead.y = nextY;
			newHead.x = nextX;

			snake.push_front(newHead);

			if (arr[nextY][nextX] == 1) { // 사과라면
				arr[nextY][nextX] = 0; // 0으로
			}
			else {
				// 길이 유지해야 하므로 꼬리 제거
				snake.pop_back();
			}

		}

	}

	printf("%d\n", Time);

	return 0;
}


// 1. 덱 자료구조를 사용하면 수월하게 풀이 가능
// 2. 최초시작점에서 한번 이동하면 1초 지난 것!
// 3. 뱀 좌표 deque의 front 는 현재 방향 정보 가지고 있다!