[백준][삼성 SW 역량 테스트][Gold 5][C++] 3190 뱀

문제

백준 삼성 SW 역량 테스트 기출 문제 - 3190 뱀 (Gold 5)

3190번: 뱀

 

---

문제 풀이

접근 방식

사과의 위치와 뱀의 이동경로가 주어질 때, Dummy 게임이 몇 초에 끝나는 지를 구하는 문제이다.

게임 시작 시, 뱀은 맨 위 맨 좌측에 위치하며, 다음과 같이 이동한다.

 

뱀의 이동 규칙

 

우선, 입력값을 받아 map에 사과의 위치의 값을 -1로 저장해주었고,

방향 전환 시기와 방향을 각각 X, C 벡터에 저장해주었다.

뱀은 맨 앞의 값을 조회하고, 맨 앞에 값을 추가하고,

맨 뒤의 값을 제거하는 일을 수행해야 하기 때문에 deque로 구현하였다.

 

그 후, while문 내에서 뱀을 이동시켜주며 게임이 종료되는 시기를 구해주었다.

처음에는 오른쪽으로 직진하도록 구현하였고,

방향을 바꿔야 하는 시기가 되면 이동 방향을 원래 방향의 오른쪽 또는 왼쪽으로 바꿔주었다.

 

뱀이 맵을 벗어나는 경우에는 바로 while문을 종료하였고,

그렇지 않은 경우에는 뱀의 앞부분에 이동할 곳의 위치를 넣어주었다.

 

이동할 곳에 사과가 존재하지 않는다면, 뱀의 맨 뒤의 값을 제거하고 map의 해당 위치의 값을 0으로 바꿔주었다.

이동할 곳이 뱀이 위치하고 있는 곳인 경우에는 while문을 바로 종료해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, K, L;
vector<vector<int> > map;

int main() {
	// 입력 받기
	cin >> N >> K;
	map.assign(N, vector<int>(N));
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		map[a - 1][b - 1] = -1;
	}
	cin >> L;
	vector<int> X(L);
	vector<int> C(L);
	for (int i = 0; i < L; i++)	{
		char c;
		cin >> X[i] >> c;
		if (c == 'D') C[i] = 1;		// 오른쪽
		else C[i] = -1;			// 왼쪽
	}

	deque<pair<int, int>> snake;
	snake.push_front({ 0,0 });
	map[0][0] = 1;
	int dirs[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
	int answer = 0;
	int dir = 0;
	int idx = 0;
	while (1) {
		// 방향 전환
		if (idx < L && answer == X[idx]) {
			if (C[idx] == 1) dir = (dir + 1) % 4;
			else dir = (dir + 3) % 4;
			idx++;
		}
        
		// 뱀 이동
		answer++;
		int nx = snake.front().first + dirs[dir][0];
		int ny = snake.front().second + dirs[dir][1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;	// 맵을 벗어난 경우
		snake.push_front({ nx,ny });
		if (map[nx][ny] == 0) {	// 사과가 없는 경우
			map[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}
		else if (map[nx][ny] == 1) break;	// 자신에게 부딪힌 경우
		map[nx][ny] = 1;
	}
	cout << answer;
}

실행 결과

실행 결과 : 통과 (0ms)