[C++] 백준 3190 뱀

문제 링크

---

www.acmicpc.net/problem/3190

3190번: 뱀

 

접근 방법

---

 deque의 자료구조를 사용하여 어렵지 않게 구현 할 수 있는 문제였습니다. 매 시간마다 현재의 방향을 설정해줍니다. 현재 시간에 방향을 바꿔야하는 명령어가 있다면 방향을 전환합니다. 그 다음 설정된 방향으로 이동을 했을 때 4가지를 검사합니다. 

 

1. 다음 위치가 사과인지

2. 다음 위치가 뱀의 몸인지

3. 다음 위치가 벽인지(범위를 벗어났는지)

4. 다음 위치가 빈 공간인지 

 

문제에서 제시된 대로 이동에 대한 규칙은 머리를 먼저 추가합니다. 

1의 경우라면 더 이상의 처리는 없습니다.

2의 경우라면 게임을 종료합니다.

3의 경우라면 게임을 종료합니다.

4의 경우라면 가장 말단의 꼬리를 제거합니다.

 

 

소스 코드

---

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#define body 1
#define apple 2
#define wall 3

using namespace std;

typedef struct coord {
	int x;
	int y;
};

deque <coord> snake;
queue <pair<int, char>> inst;
coord direction[4] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
int N, K, L;
int map[103][103];

bool inRange(int x, int y) {
	return (0 < x && x <= N && 0 < y && y <= N) ? true : false;
}

int nextSquare(coord head, int dir) {
	
	coord nextcoord = { head.x + direction[dir].x, head.y + direction[dir].y };

	if (map[nextcoord.x][nextcoord.y] == apple)
		return apple;
	else if (map[nextcoord.x][nextcoord.y] == body)
		return body;
	else if (!inRange(nextcoord.x, nextcoord.y))
		return wall;
	else
		return 0;
}

int change_dir(int dir, char inst) {

	dir += 4;
	if (inst == 'L')
		return (dir - 1) % 4;
	else
		return (dir + 1) % 4;
}

int now_dir(int cnt, int dir) {

	int newdir = dir;

	if (!inst.empty() && inst.front().first == cnt) {
		newdir = change_dir(dir, inst.front().second);
		inst.pop();
	}
	return newdir;
}

bool go(int dir) {
	
	coord head = snake.back();
	
	int nextState = nextSquare(head, dir);
	coord nextcoord = { head.x + direction[dir].x, head.y + direction[dir].y };
	
	snake.push_back(nextcoord);
	map[snake.back().x][snake.back().y] = body;

	if (nextState == apple) {
		return true;
	}
	else if (nextState == body) {
		return false;
	}
	else if (nextState == wall) {
		return false;
	}
	else {
		map[snake.front().x][snake.front().y] = 0;
		snake.pop_front();
		return true;
	}

}

int solve() {

	int cnt = 0;
	int dir = 0;
	
	snake.push_back({ 1,1 });
	map[1][1] = body;
	
	while (true) {
		//printmap();
		dir = now_dir(cnt, dir);
		cnt++;
		if (!go(dir))
			break;
	}
	return cnt;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;

	cin >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		map[x][y] = apple;
	}

	cin >> L;
	for (int i = 0; i < L; i++) {
		int t; char dir;
		cin >> t >> dir;
		inst.push({ t, dir });
	}

	cout << solve() << endl;

}

개발 환경 : VS2017

질문, 지적 환영합니다!