Algorithm

[BAEKJOON] 3190 뱀

0so0 2023. 8. 17. 19:00
728x90
반응형
SMALL

백준 3190 뱀 풀이 정리
 
3190 뱀

문제 

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
 
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
 
입력

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
 
 
출력

9

 

풀이

입력받는 뱀의 방향 전환 정보를 큐에 저장한 뒤 이동 규칙에 따라 이동시키며 풀이하면 됨

 

1. 뱀의 이동 방향을 dx, dy로 정의 => 뱀의 최초 이동 방향은 오른쪽이므로 인덱스는 3으로 설정해야함

// 상 하 좌 우
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

2. 뱀이 존재하는 위치 정보를 저장하는 deque 선언하여 뱀의 머리, 꼬리 판단

// 뱀의 존재 위치 정보 저장 deque
deque <pair<int, int>> position;

 

3. 이동 방향에 따라 뱀의 좌표를 이동시키고 유효한 범위인지, 뱀이 존재하는 위치인지 체크

int nx = x + dx[diridx];
int ny = y + dy[diridx];

// 유효한 범위이고 뱀이 존재하는 위치가 아니면
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && graph[nx][ny] != 2) {
}
// 벽이나 뱀과 부딪혔으면
else {
	time++;
	break;
}

4. 사과가 있다면 뱀의 머리 위치 변경, position의 맨 앞에 업데이트

// 사과가 있으면 뱀의 머리 위치를 바꾸고 position 덱의 맨 앞에 업데이트
if (graph[nx][ny] == 1) {
	graph[nx][ny] = 2;
	position.push_front({ nx, ny });}

5. 사과가 없다면 뱀의 머리 위치 변경, position의 맨 앞에 업데이트, 꼬리 위치를 position에서 제거하고 맵에서 초기화

// 사과가 없으면 뱀의 머리 위치 바꾸고 pisiton 덱의 맨 앞에 업데이트, 꼬리 위치 position 덱에서 제거
if (graph[nx][ny] == 0) {
	graph[nx][ny] = 2;
	position.push_front({ nx, ny });

	graph[position.back().first][position.back().second] = 0;
	position.pop_back();}

6. x, y 좌표 변경 후 시간 증가

x = nx;
y = ny
time++;

7. 뱀의 방향 정보를 저장한 q에서 시간과 방향을 받아 방향을 변경할 시간일 경우 방향 변경

if (!q.empty() && time == q.front().first) {
	char newdir = q.front().second;
	q.pop();
	switch (diridx) {
	// 올라갈때
	case 0:
		// 왼쪽방향이면 왼쪽으로
		if (newdir == 'L') diridx = 2;
		// 오른쪽 방향이면 오른쪽으로
		else diridx = 3;
		break;
	// 내려갈때
	case 1:
		// 왼쪽 방향이면 오른쪽으로
		if (newdir == 'L') diridx = 3;
		// 오른쪽 방향이면 왼쪽으로
		else diridx = 2;
		break;
	// 왼쪽 갈때
	case 2:
		// 왼쪽 방향이면 아래쪽으로
		if (newdir == 'L') diridx = 1;
		// 오른쪽 방향이면 윗쪽으로
		else diridx = 0;
		break;
	// 오른쪽 갈때
	case 3:
		// 왼쪽 방향이면 윗쪽으로
		if (newdir == 'L') diridx = 0;
		// 오른쪽 방향이면 아래쪽으로
		else diridx = 1;
		break;
	}
}

 

디버깅시 아래 전체 코드에 주석처리해놓은 print함수를 이용하면 편리함

전체 코드

더보기 
#include <iostream>
#include <queue>

using namespace std;

// 보드의 크기, 사과의 개수, 뱀의 방향 변환 횟수
int n, k, l;

// 뱀의 방향 변환 정보 저장 q
queue <pair<int, char>> q;

// 뱀의 존재 위치 정보 저장 q
deque <pair<int, int>> position;

// 사과 위치 정보 저장 배열
int graph[101][101];

// 상 하 좌 우
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void print() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << graph[i][j] << " ";
		}
		cout << endl;
	}

	cout << "\n" << endl;
}


int snake() {
	int x = 1, y = 1; // 뱀의 머리 위치
	int time = 0;
	int diridx = 3; // 처음 방향은 오른쪽
	graph[x][y] = 2; // 뱀이 존재하는 위치는 2로 표시
	position.push_front({ x, y });

	while (1) {
		int nx = x + dx[diridx];
		int ny = y + dy[diridx];

		// 유효한 범위이고 뱀이 존재하는 위치가 아니면
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && graph[nx][ny] != 2) {
			// 사과가 있으면 뱀의 머리 위치를 바꾸고 position 덱의 맨 앞에 업데이트
			if (graph[nx][ny] == 1) {
				graph[nx][ny] = 2;
				position.push_front({ nx, ny });
			}
			// 사과가 없으면 뱀의 머리 위치 바꾸고 pisiton 덱의 맨 앞에 업데이트, 꼬리 위치 position 덱에서 제거
			if (graph[nx][ny] == 0) {
				graph[nx][ny] = 2;
				position.push_front({ nx, ny });

				graph[position.back().first][position.back().second] = 0;
				position.pop_back();
			}
		}
		// 벽이나 뱀과 부딪혔으면
		else {
			time++;
			break;
		}

		x = nx;
		y = ny;

		time++;

		if (!q.empty() && time == q.front().first) {
			char newdir = q.front().second;
			q.pop();
			switch (diridx) {
			// 올라갈때
			case 0:
				// 왼쪽방향이면 왼쪽으로
				if (newdir == 'L') diridx = 2;
				// 오른쪽 방향이면 오른쪽으로
				else diridx = 3;
				break;
			// 내려갈때
			case 1:
				// 왼쪽 방향이면 오른쪽으로
				if (newdir == 'L') diridx = 3;
				// 오른쪽 방향이면 왼쪽으로
				else diridx = 2;
				break;
			// 왼쪽 갈때
			case 2:
				// 왼쪽 방향이면 아래쪽으로
				if (newdir == 'L') diridx = 1;
				// 오른쪽 방향이면 윗쪽으로
				else diridx = 0;
				break;
			// 오른쪽 갈때
			case 3:
				// 왼쪽 방향이면 윗쪽으로
				if (newdir == 'L') diridx = 0;
				// 오른쪽 방향이면 아래쪽으로
				else diridx = 1;
				break;
			}
		}
		//cout << time << endl;
		//print();
	}

	return time;
}

int main(void) {
	cin >> n;

	cin >> k;

	for (int i = 0; i < k; i++) {
		// 사과의 위치 행, 열
		int x, y;
		cin >> x >> y;
		graph[x][y] = 1;
	}

	// 뱀의 방향 변환 횟수
	cin >> l;

	for (int i = 0; i < l; i++) {
		// 뱀의 방향 변환 정보 - x초 뒤 c(왼쪽이나 오른쪽)로 방향 회전
		int x;
		char c;
		//x초 뒤 c(왼쪽이나 오른쪽)로 방향 회전
		cin >> x >> c;
		q.push({ x, c });
	}

	//print();

	cout << snake() << endl;

	return 0;
}

 

728x90
반응형
LIST

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 11724 연결 요소의 개수  (0) 2023.08.24
[Programmers] 타겟 넘버  (0) 2023.08.23
[BAEKJOON] 18406 럭키 스트레이트  (0) 2023.08.14
[BAEKJOON] 1439 뒤집기  (0) 2023.08.14
[BAEKJOON] 7576 토마토  (0) 2023.08.10

'Algorithm'의 다른글

  • 현재글[BAEKJOON] 3190 뱀

관련글

티스토리툴바