백준 3190번 _ 뱀

2020-04-19 · 배운 것 · 5분 읽기

https://www.acmicpc.net/problem/3190

3190번: 뱀

풀이방법

이 문제는 자료형만 적절히 선언한다면 매우 직관적이고 풀기 쉬운 문제다.

나는 밑과 같이 자료형을 선언하였다.

queue<pair<int, int>> snake;	//뱀의 이동경로 저장과 삭제를 용이하기 위해서 que로 선언
set<pair<int, int>> snakeBody;	//자기 자신과 부딪쳤는지 확인을 용이하기 위한 set
map<int, char> changeTime;		//이동 경로가 언제바뀌는지 알수있게 해주는 map
int board[102][102];		
int N, K, L;			
int dy[] = {0, 0, -1, 1, 0 };	// 우 (1), 상 (2), 하(3), 좌(4) 
int dx[] = {0, 1, 0, 0, -1 };

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>

using namespace std;

queue<pair<int, int>> snake;
set<pair<int, int>> snakeBody;
map<int, char> changeTime;
int board[102][102];
int N, K, L;
int dy[] = {0, 0, -1, 1, 0 };
int dx[] = {0, 1, 0, 0, -1 };

void Input()
{
	cin >> N;
	cin >> K;
	int y, x;
	for (int i = 0; i < K; i++)
	{
		cin >> y >> x;
		board[y][x] = 1;
	}
	cin >> L;
	int time;
	char turnDir;
	for (int i = 0; i < L; i++)
	{
		cin >> time >> turnDir;
		changeTime[time] = turnDir;
	}
}

int changeDirection(int dir, char turn)
{
	if (dir == 1)
	{
		if (turn == 'L')
			return 2;
		else
			return 3;
	}
	else if (dir == 2)
	{
		if (turn == 'L')
			return 4;
		else
			return 1;
	}
	else if (dir == 3)
	{
		if (turn == 'L')
			return 1;
		else
			return 4;
	}
	else if (dir == 4)
	{
		if (turn == 'L')
			return 3;
		else
			return 2;
	}
}

int game()
{
	snake.push({ 1,1 });
	snakeBody.insert({ 1, 1 });
	int dir = 1;
	int time = 0;
	int y= 1, x = 1;
	while (1)
	{
		time++;
		//뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		//범위를 넘거나 자기자신에게 부딪혔는지 확인
		if ((ny >= 1 && nx >= 1 && ny <= N && nx <= N) == false)
			break;
		if (snakeBody.count({ ny, nx }) > 0)
			break;

		snake.push({ ny, nx });
		snakeBody.insert({ ny, nx });

		//이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
		if (board[ny][nx] == 0)
		{
			auto erasePos = snake.front();
			snake.pop();
			snakeBody.erase(snakeBody.find(erasePos));
		}
		else
			board[ny][nx] = 0;

		//방향이 변하는지 확인하고 
		if (changeTime.count(time) > 0)
		{
			dir = changeDirection(dir, changeTime[time]);
		}
		y = ny;
		x = nx;
	}
	return time;
}

int main()
{
	Input();
	cout << game();
	return 0;
}

후기

내 개인적으로는 삼성 기출문제중에서는 제일 쉬운 문제인것 같다.