백준 3190

백준 3190 : 뱀

1. 입력받기
2. 뱀이 이동할 거리와 방향을 큐에다 저장
3. 큐 값들을 하나씩 빼내면서 뱀의 이동을 구현

뱀의 길이가 늘어나는 부분을 어떻게 해야 할까?
sol) 뱀의 위치를 덱을 이용해 처리한다.

뱀 몸통 각각의 위치를 덱을 이용해 저장한다.
사과를 먹는다면 덱의 front에 push만 하면 되고,
사과를 먹지 않았다면 front에 push한 뒤 back에서 pop하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, k, L, X;
char C;
int board[101][101];
queue<pair<int, int>> movement; //이동 방향과 거리 정보
int ny, nx;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int nd;
int ans;
deque<pair<int, int>> snake_q;  //뱀이 차지하고 있는 위치
int snakeMap[101][101];
int timeElapsed; 				//경과 시간 


void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int apple_x, apple_y;
	
	cin>>n>>k;
	for(int i=0; i<k; i++) {
		cin>>apple_y>>apple_x;
		board[apple_y-1][apple_x-1]=1;
	} 
	
	cin>>L;
	
	for(int i=0; i<L; i++) {
		cin>>X>>C;
		movement.push({X, C});
	}
		
}


//print for test
void print_snake() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cout<<board[i][j]<<' ';
		}
		cout<<'\t';
		
		for(int j=0; j<n; j++) {
			cout<<snakeMap[i][j]<<' ';
		}
		cout<<'\n';
	}
	
	cout<<'\n';
}


//get movements and direction
void moveSnake(int times, char direction, int now_x, int now_y) {
	while(times--) {
		ny = now_y+dy[nd];
		nx = now_x+dx[nd];
		timeElapsed++; 
		
		if(ny<0 || nx<0 || ny>=n || nx>=n || snakeMap[ny][nx]==5) { //game ends
			cout<<timeElapsed<<'\n';
			exit(0);
		}
		
		//if game does not end
		//snake extended
		snake_q.push_front({ny, nx});
		snakeMap[ny][nx] = 5; //update snake map
		
		//if there is no apple: remove tail
		if(board[ny][nx]==0) {
			snakeMap[snake_q.back().first][snake_q.back().second]=0;
			snake_q.pop_back();
		} 
		
		//apple has eaten
		board[ny][nx] = 0;
		
//		print_snake();
		
		
		//update current location to next
		now_y = ny;
		now_x = nx;
		
	}
	
	//change direction 
	if(direction=='D') { //rotate right
		nd = (nd+1)%4;
	}
	else { //rotate left
		nd = (nd+3)%4;
	}
}



int main() {	
	input();
	
	nd=0;
	snake_q.push_back({0, 0}); //시작 위치 지정
	snakeMap[0][0] = 5;
	
//	int moveDistance = movement.front().first;
//	char direction = movement.front().second;
//	
//	print_snake();
	

	while(movement.size()) {
		int moveDistance = movement.front().first;
		moveDistance -= timeElapsed;
		char direction = movement.front().second;
		
		moveSnake(moveDistance, direction, nx, ny);
		movement.pop();
	}
	
	moveSnake(10000, nd, nx, ny);
	

	return 0;
}

---

최초 제출한 오답 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, k;
int board[101][101];
int L, X;
char C;
queue<pair<int, char>> movement;
int ny, nx;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int nd;
int ans;
deque<pair<int, int>> snake_q;
int snakeMap[101][101];
int timeElapsed;

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int apple_x, apple_y;
	
	cin>>n>>k;
	for(int i=0; i<k; i++) {
		cin>>apple_y>>apple_x;
		board[apple_y-1][apple_x-1] = 1;
	}
	
	cin>>L;
	
	
	for(int i=0; i<L; i++) {
		cin>>X>>C;
		movement.push({X, C});
	}
}


//print for test
void print_snake() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cout<<board[i][j]<<' ';
		}
		cout<<'\t';
		
		for(int j=0; j<n; j++) {
			cout<<snakeMap[i][j]<<' ';
		}
		cout<<'\n';
	}
	
	cout<<'\n';
}

//get movements and direction 
void moveSnake(int times, char direction, int now_y, int now_x) {
	while(1) {
		ny = now_y+dy[nd];
		nx = now_x+dx[nd];
		timeElapsed++;
		
		if(ny<0 || nx<0 || ny>=n || nx>=n || snakeMap[ny][nx]==5) { //game ends
			cout<<timeElapsed<<'\n';
			exit(0);
		}
		
		//snake extended 
		snake_q.push_front({ny, nx});
		snakeMap[ny][nx]=5;
		
		//if there is no apple: remove tail
		if(board[ny][nx] == 0) {
			snakeMap[snake_q.back().first][snake_q.back().second]=0;
			snake_q.pop_back();
		}
		
		//apple has eaten
		board[ny][nx] = 0;
		
		print_snake();
		
		now_y = ny;
		now_x = nx;
		
		//break if time is out
		if(timeElapsed == times) {
			break;
		}
	}
	
	//change direction
	if(direction=='D') { //rotate right
		nd = (nd+1)%4;
	}
	else if(direction=='L') { //rotate left
		nd = (nd+3)%4;
	}
}


int main() {	

	input();
	
	nd = 0;
	snake_q.push_back({0, 0});
	snakeMap[0][0] = 5;
	
	int times = movement.front().first;
	char direction = movement.front().second;
	
	print_snake();
	
	while(movement.size()) {
		times = movement.front().first;
		direction = movement.front().second;
		
		moveSnake(times, direction, ny, nx);
		movement.pop();
	}
	
	return 0;
}

---

예제 입력 2번의 경우에 벽에 부딪히고 나서 진행이 안된다
-> 반복 횟수에 부딪혀서 그런건가?

이 부분을 어떻게 고쳐볼까

//break if time is out
if(timeElapsed == times) {
    break;
}

break 문에 자꾸 끊겨 종료돼서 맨 마지막에 직진하는 부분이 제대로 실행이 안되고 있었다.
-> 맨 마지막에 한번 더 moveSnake 함수를 호출하는 것으로 해결하였다!