백준 3190 - 뱀(C++)

문제 링크입니다. https://www.acmicpc.net/problem/3190

3190번: 뱀

삼성 SW 역량테스트 문제입니다.

Deque을 사용하면 풀 수 있는 문제였습니다.

문제 조건

출력 예시

뱀의 현재 위치와 이동했을 때, 뱀의 머리가 몸통에 닿는지를 확인해야 했습니다.

저는 Deque을 사용하여 front에는 머리 위치, back에는 꼬리 위치를 저장하여 풀었습니다.

이동할 때마다, 꼬리 위치인 back를 pop해주고, 새로운 머리 위치를 front에 push를 해주면서 뱀의 위치를 계속 갱신했습니다.

 

1. 뱀의 방향 바꾸기

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void change_snake(int num) {
	if (way == 0) {
		if (change_way[num].second == 'L') way = 2;
		else way = 3;
	}
	else if (way == 1) {
		if (change_way[num].second == 'L') way = 3;
		else way = 2;
	}
	else if (way == 2) {
		if (change_way[num].second == 'L') way = 1;
		else way = 0;
	}
	else {
		if (change_way[num].second == 'L') way = 0;
		else way = 1;
	}
}

L이 입력되었을 때는 왼쪽으로 90도 이동하고, D가 입력되었을 때는 오른쪽으로 90도를 이동해야합니다.

현재 이동 방향이 오른쪽일때, L이 입력되면 위쪽으로 움직이며 D가 입력되면 아래쪽으로 움직입니다.

현재 이동 방향이 위쪽일때, L이 입력되면 아래쪽으로 움직이며 D가 입력되면 위쪽으로 움직입니다.

 

이런 방식을 통해 방향 전환을 구현했습니다.

 

2. 뱀의 움직임 구현하기

void move_snake(int cnt, int way) {
	int x = snake.front().first + dx[way];
	int y = snake.front().second + dy[way];
	if (x >= 1 && x <= N && y >= 1 && y <= N) {
		if (map[x][y] != 1) {
			if (map[x][y] == 9) {
				snake.push_front(make_pair(x, y));
				map[x][y] = 1;
			}
			else {
				map[x][y] = 1;
				map[snake.back().first][snake.back().second] = 0;
				snake.push_front(make_pair(x, y));
				snake.pop_back();	
			}
		}
		else {
			flag = 1;
		}
	}
	else flag = 1;
}

snake deque에는 뱀의 현재 위치가 저장되어 있습니다. front에는 뱀의 머리 위치가 저장되어 있음으로 front를 통해 뱀의 다음 이동 위치를 구했습니다.

또한 map[X][Y]의 값이 1이라면, 해당 좌표에 뱀의 몸이 있다는 의미이며, 값이 9라면 사과가 있다는 의미입니다.

 

뱀의 다음 위치가 MAP을 벗어나지 않으면서, MAP의 값이 1이 아닌 경우에 뱀이 이동할 수 있습니다.

만약, MAP을 벗어나거나 MAP의 값이 1이라면 더이상 이동할 수 없음으로 flag 값을 1로 바꿨습니다.

 

뱀이 이동한 곳이 사과가 있을 경우, 꼬리 부분을 pop을 하지 말아야합니다.

 

 

3. 그외

pair<int, char> change_way[10001];

이동하면서 방향이 변하는 값을 저장해야합니다.

이동 시간의 범위가 10000까지이니, 저는 배열을 통해, 방향이 변하는 곳의 값을 1로 만들어줬습니다.

따라서 X번째 배열의 값이 1이라면, 방향을 변환해줬습니다.

 

 

문제 접근 방법

1. 1초부터 시작하여 뱀의 위치를 이동하기

2. X초에서 방향을 변환해야 한다면 방향을 바꿔주기

3. 만약에 이동할 수 없을 경우, 이동 시간을 출력하고 끝내기

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N, K, L, flag;
pair<int, int> apple[101];
int map[101][101];
pair<int, int> start = { 1,1 };
pair<int, char> change_way[10001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
deque<pair<int, int>> snake;
int cnt = 1, way = 2;

void change_snake(int num) {
	if (way == 0) {
		if (change_way[num].second == 'L') way = 2;
		else way = 3;
	}
	else if (way == 1) {
		if (change_way[num].second == 'L') way = 3;
		else way = 2;
	}
	else if (way == 2) {
		if (change_way[num].second == 'L') way = 1;
		else way = 0;
	}
	else {
		if (change_way[num].second == 'L') way = 0;
		else way = 1;
	}
}

void move_snake(int cnt, int way) {
	int x = snake.front().first + dx[way];
	int y = snake.front().second + dy[way];
	if (x >= 1 && x <= N && y >= 1 && y <= N) {
		if (map[x][y] != 1) {
			if (map[x][y] == 9) {
				snake.push_front(make_pair(x, y));
				map[x][y] = 1;
			}
			else {
				map[x][y] = 1;
				map[snake.back().first][snake.back().second] = 0;
				snake.push_front(make_pair(x, y));
				snake.pop_back();	
			}
		}
		else {
			flag = 1;
		}
	}
	else flag = 1;
}

void solve() {
	snake.push_front(start);
	map[start.first][start.second] = 1;              
	while (1) {
		if (flag == 1) {
			cout << cnt;
			break;
		}
		move_snake(cnt, way);
		if (change_way[cnt].first == 1) {
			change_snake(cnt);
		}
		if(flag == 0) cnt++;
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		cin >> apple[i].first >> apple[i].second;
		map[apple[i].first][apple[i].second] = 9;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		int x;
		char y;
		cin >> x >> y;
		change_way[x] = { 1,y };
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!