백준 3190 뱀

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 뱀이 위치할때 주어진 방향으로 뱀이 이동하며 그위치에 사과가 있으면 꼬리를 그냥두고 사과가 없으면 꼬리를 자르면서 벽이나 자기몸을 만날때 까지 몇초가 걸렸는지 구하는 문제입니다. 저는 뱀이 위치한 곳은 2로 사과가 위치한 곳은 1로 값을 정하고 주어진대로 구현을 하면 되는 문제입니다. 주의할 점은 방향 변환은 이동이 끝난 후에 일어나므로 이점을 주의해야 할 것 같습니다. 또 방향은 왼쪽과 오른쪽이 존재하므로 각 인덱스를 +1, -1 해준다고 생각하면 됩니다.

 

다음은 코드입니다.

 

 

 #include <iostream>
#include <queue>

using namespace std;

int board[101][101];
int N,K,L;
queue<pair<int, char> > chdir; // 방향 변환에 대한 정보 
queue<pair<pair<int, int>, int> > snake; //뱀의 형태에 대한 정보 + 위치에서의 방향 
//북동남서 0 1 2 3
int nextx[4] = {-1, 0, 1, 0};
int nexty[4] = {0, 1, 0, -1};
int sec = 0;

void search() {
	
	while(!snake.empty()) {
		sec++;
		int x = snake.back().first.first;
		int y = snake.back().first.second;
		int dir = snake.back().second;
		 
		int xx = x + nextx[dir];
		int yy = y + nexty[dir];
		
		if(board[xx][yy] == 2 || xx < 1 || xx > N || yy < 1 || yy > N)
			break;
		
		if(board[xx][yy] == 0) {
			board[snake.front().first.first][snake.front().first.second] = 0; // 꼬리가 짤림 
			snake.pop();
		}
		
		if(board[xx][yy] == 1) // 사과 먹음 
			board[xx][yy] = 0; 
		
		board[xx][yy] = 2; //뱀 몸 
		
		if(!chdir.empty()) 
			if(sec == chdir.front().first) { // 시간이 되어 방향을 회전할때 
				if(chdir.front().second == 'D') 
					dir = (dir+1) % 4;
				else
					dir = (dir+4-1) % 4;
				
				chdir.pop();

			}
		
		snake.push(make_pair(make_pair(xx, yy), dir));
	}
} 

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> K;
	
	for(int i = 0; i < K; i++) {
		int x,y;
		cin >> x >> y;
		board[x][y] = 1; //1은 사과가 있음 
	}
		
	cin >> L;
	
	for(int i = 0; i < L; i++) {
		int n;
		char a;
		cin >> n >> a;
		chdir.push(make_pair(n, a));
	}
	
	snake.push(make_pair(make_pair(1,1), 1));
	board[1][1] = 2; //뱀의 몸은 2로 표시 
	search();
	cout<<sec;	
	return 0;
}