[ Baekjoon ] 3190. 뱀

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

3190번: 뱀

풀이 방법

뱀의 위치, 움직임, 회전 등을 Snake라는 클래스로 나타냈다.

enum Dir{RIGHT, DOWN, LEFT, UP};

class Snake{
public:
	Snake(): dir(RIGHT) {
		body.push_front(0);
		body_pos.insert(0);
	};
	void rotate(int d){
		if(d == RIGHT) dir = (dir + 1) % 4;
		else dir = (dir +  3) % 4;
	}
	bool move();

private:
	int dir;
	unordered_set<int> body_pos;
	deque<int> body;
};

구현의 용이성을 위해 N*N 배열에서 (r, c)의 위치를 (r*N + c)로 계산하여 2차원 좌표를 1차원으로 변환해 저장하도록 했다.

 

뱀의 위치를 저장하는 자료구조는 두가지인데, body_pos는 뱀이 자신의 몸에 부딪히는 것을 쉽고 빠르게 확인하기 위한 변수이고, 덱 body는 뱀이 머리를 먼저 앞으로 늘리고 꼬리를 잡아당기는 특성을 고려한 변수이다. 덱의 front쪽이 뱀의 머리이다.

 

dir은 뱀이 나아가는 방향이다. rotate() 메소드는 회전하는 방향에 따라 dir을 업데이트한다.

 

 

뱀이 한번 움직이는 것을 move() 메소드로 구현했다. 정상적으로 움직였다면 true, 그렇지 않은 경우 false를 반환한다.

 

우선 오른쪽, 아래쪽, 왼쪽, 위쪽 순으로 델타 배열을 정의하고 뱀이 나아가는 방향으로 움직였을 때 위치를 next_r, next_c,  next_pos에 각각 저장했다.

const static int dr[4] = {0, 1, 0, -1}; // RIGHT, DOWN, LEFT, UP
const static int dc[4] = {1, 0, -1, 0};

int next_r = body.front() / N + dr[dir];
int next_c = body.front() % N + dc[dir];
int next_pos = body.front() + dr[dir]*N + dc[dir];

움직였을 때 자신의 몸 또는 벽에 부딪혔는지 확인한다.

// check collision with body
if(body_pos.find(next_pos) != body_pos.end()) return false;

// check collision with wall
if(next_r < 0 || next_r >= N || next_c < 0 || next_c >= N) return false;

정상적으로 움직일 수 있다면 관련 변수들을 업데이트 한 후, 해당 위치에 사과가 있는지 확인한다. 사과가 없다면 꼬리를 움직이고, 그렇지 않으면 꼬리는 그대로 유지한 채 사과를 먹는다.

// move forward
body.push_front(next_pos);
body_pos.insert(next_pos);
if(apples.find(next_pos) == apples.end()){ // apple doesn't exists
	int tail = body.back();
	body.pop_back();
	body_pos.erase(tail);
}
else{ 
	apples.erase(next_pos);
}

 

전체 코드는 여기서 확인할 수 있다.