[백준 3190] 뱀

덱을 쓰는 오늘날의 나.. 강해졌지만 실수를 한다 ㅋㅋㅋ.. 안귀엽다

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

3190번: 뱀

#include <cstdio>
#include <queue>
int N; 
int K;
int board[100 + 2][100 + 2];	// 사과 1 빈칸 0
int L;
char CMD[10000 + 2];

struct _st
{
	int x, y;
};
std::deque<_st> S;

void input()
{
	scanf("%d", &N);
	scanf("%d", &K);
	for (int k = 0; k < K; k++) {
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		board[x][y] = 1;
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		int t = 0; char d = '0';
		scanf("%d %c", &t, &d);
		CMD[t] = d;
	}
}


int simul()
{
	// 0우 1하 2좌 3상
	int dir_x[4] = { 0, 1, 0, -1 };
	int dir_y[4] = { 1, 0, -1, 0 };

	int time = 1;
	int p = 0;	// 뱀은 처음에 오른쪽을 향한다. 
	S.push_front({ 1, 1 });

	while (1) {
		int nx = S.front().x + dir_x[p];
		int ny = S.front().y + dir_y[p];

		if (nx < 1 || nx > N || ny < 1 || ny > N) return time;
		for (auto iter = S.begin(); iter != S.end(); iter++) {
			if (nx == iter->x && ny == iter->y) return time;
		}

		if (board[nx][ny] == 1) {
			S.push_front({ nx, ny });
			board[nx][ny] = 0;
		}
		else {
			S.push_front({ nx, ny });
			S.pop_back();
		}

		if (CMD[time] != '\0') {
			if (CMD[time] == 'D') p = (p + 1) % 4;
			else p = (p + 3) % 4;
		}
		//debug(time);
		time++;
	}
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

 

문제에서  "X는 10,000 이하의 양의 정수"이다. 그러면 CMD 배열이 100까지 있어야 할 까 10000까지 있어야 할까 ?

생각이라는 것을 하고 문제를 푸는 것일까 ?

---

큐를 쓰고 좋아하는 지난날의 나.. 커엽내..

#include <cstdio>
#include <iostream>
#include <queue>
int N;
int K;
int map[100 + 10][100 + 10];
int L;
struct _st
{
	int X;
	char C;
}move[100 + 10];

struct _snake
{
	int x;
	int y;
};
std::queue<_snake> Q;

int dir_x[4] = { 0, 1, 0, -1 };	// RDLU
int dir_y[4] = { 1, 0, -1, 0 };


void input(void)
{
	scanf("%d %d", &N, &K);
	for (int i = 0; i < K; i++) {
		int r = 0; int c = 0;
		scanf("%d %d", &r, &c);
		map[r][c] = 1;		// 과일위치 표시
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		scanf("%d %c", &move[i].X, &move[i].C);
	}
}


int game(void)
{
	Q.push({ 1, 1 });	// 뱀은 (1, 1)에서 시작

	int x = 1; int y = 1; int p = 0; 
	int time = 0; int n = 0;
	for (;;) {
		map[x][y] = 2;	// 뱀 표시

		int nx = x + dir_x[p];	// 전진
		int ny = y + dir_y[p];
		if (nx < 1 || nx > N || ny < 1 || ny > N || map[nx][ny] == 2) return time;
		
		x = nx; y = ny;
		Q.push({ x, y });	// 머리부분 채우기
		if (map[x][y] != 1) {
			map[Q.front().x][Q.front().y] = 0;	// 꼬리부분 비우기
			Q.pop();	
		}
		
		time += 1;	// 시간 계산
		if (time == move[n].X) {
			if (move[n].C == 'D') p = (p + 1) % 4;
			else if (move[n].C == 'L') p = (p + 3) % 4;
			n += 1;
		}
	}


}

int main()
{
	input();
	int ans = game();
	printf("%d", ans + 1);
	return 0;
}

뱀이 과일을 만나면 몸통의 길이를 1 늘려주고, 과일을 만나지 않으면 꼬리가 위치한 칸을 비워 몸통의 길이를 줄여야 하기 때문에 "큐" 자료구조를 사용했다. 가장 처음 큐에 삽입한 원소를 pop 해주어 꼬리 칸을 삭제하는 방식이다. 

 

그리고 이거 풀면서 큐에서 구조체 어떻게 쓰는건지 배웠다. 진짜 신기 했던건 뱀의 꼬리칸을 비울 때 큐에 저장했던 x, y좌표를 "Q.front().x" "Q.front().y"  이런식으로 뺄 수 있다는 점....너무 간편 구조체 짱이다

 

 

// game( ) 함수

뱀은 무조건 (1, 1)에서 시작한다고 했으니까, 큐에 ({1, 1})을 삽입한다.

그리고 "뱀이 자기 몸에 부딪혀 게임이 끝나는 경우"를 고려하기 위해  x = 1, y = 1부터 시작하여 뱀의 몸통을 맵에 표시(map[x][y] =  2) 해준다.

그리고 만약 벽을 만나면, 즉 map의 범위를 벗어나면 동일하게 게임이 끝나야 한다. 

 

한편 갱신한 좌표(x = nx, y = ny)를 큐에 삽입하고, 갱신한 좌표에 과일이 존재하지 않으면(map[x][y] != 1)  꼬리칸을 0으로 초기화하고, 큐에서 해당 칸의 좌표를 꺼낸다. 만약 과일이 존재하면 해당 동작은 수행하지 않는다. 

 

마지막으로 time변수를 두어 for문이 한 번 돌아갈 때 마다 1초씩 더해주는데, 만약 게임 시작 시간으로 부터 X초 후가 되면, C방향으로 전환하기 위해 p 변수를 두었다. 이를 위해 방향벡터 dir_x, dir_y 배열을 만들었는데, 그 순서는 'D(오른쪽으로 90도 회전)'를 기준으로 우 -> 하 -> 좌 -> 상 이다. 만약 'L(왼쪽으로 90도 회전)' 이라면 우 -> 상 -> 좌 -> 하 이기 때문에 (p + 3) % 4 을 해주었다. 

 

// printf("%d", ans + 1);

마지막 출력부분에서 + 1을 해준 이유는, game 함수를 돌면서 벽에 부딪히거나 자기 자신의 몸에 부딪히면 바로 time 변수를 리턴하도록 구현했기 때문이다. 그 부딪힌 시점의 시간이 더해지지 않았기 때문에 1을 더해 출력해주었다.