본문 바로가기

Computer Science&Engineering/코딩테스트

[백준 3190] 뱀 C++

# 문제링크

www.acmicpc.net/problem/3190

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

C++의 deque 를 사용해서 풀었다. 앞으로 갈 때는 push_front() 해주고, 사과가 없을 때는 pop_back() 해주었다. 방향은 이차원 배열을 만들어서 해결했다. dir[i][k] 배열은 현재 i 방향일 때 k (왼쪽이나 오른쪽)으로 움직이는 방향이다. 잘 하시는 분들은 뭔가 방향 이동에서도 규칙성을 찾으시겠지만, 나는 그냥 배열로 다 써주었다.. 

 

앞으로 갈 때마다 벽이랑 부딪혔는지, 자기 몸이랑 부딪혔는지 체크해준다. 몸과 부딪힌거는 dq 배열을 for문 돌면서 해결했다. 원래 queue 는 iter 도 안되고, 괄호로 접근하는 것도 안되는 걸로 알고있는데 deque 는 너무 편하다. 앞으로 deque 만 쓰고싶다.. 

 

# 제출 코드 

 

#include <cstdio>
#include <deque>
using namespace std;

int N;
int map[105][105];
int K;
int L;
struct st {
	int x;
	int d;
};
st info[101];
int num;
deque <pair<int, int>> dq;

void Input() {
	scanf("%d", &N);
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = 1; // 사과 위치 표시
	}
	scanf("%d", &L);
	char w;
	for (int i = 0; i < L; i++) {
		scanf("%d %1c", &info[i].x, &w);
		if (w == 'L') info[i].d = 0; // 왼쪽은 0
		else info[i].d = 1; // 오른쪽은 1
	}
}
int yd[] = { 0, 0, -1, 1 }; // 우, 좌, 상 , 하
int xd[] = { 1, -1, 0, 0 };

// dir[i][j] = 현재 i 일때 j 방향, 왼쪽은 0, 오른쪽은 1 
int dir[4][2] = {
	2, 3, 
	3, 2,
	1, 0,
	0, 1
};

int Simul() {
	dq.push_back({ 1,1 }); // 시작 
	int head_y, head_x;
	int d = 0;
	int change = 0;
	int time = 0;
	while (true) {
		head_y = dq.front().first;
		head_x = dq.front().second;

		if (info[change].x == time && change < L) {
			d = dir[d][info[change].d];
			change++;
		}
		int ny = head_y + yd[d];
		int nx = head_x + xd[d];

		if (ny < 1 || ny > N) break; // 벽만남
		if (nx < 1 || nx > N) break;
		for (int i = 0; i < dq.size(); i++) { // 몸과 부딪힘
			if (ny == dq[i].first && nx == dq[i].second) return time + 1;
		}

		dq.push_front({ ny, nx });

		if (map[ny][nx] == 1) { // 사과가 있으면 
			map[ny][nx] = 0;
		}
		else { // 사과가 없으면 
			dq.pop_back();
		}
		time++;
	}
	return time + 1;
}
int main() {
	Input();
	printf("%d\n", Simul());
}
반응형