[백준] 3190 뱀문제 c++ 구현

 

목차

 

 

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

3190번: 뱀

 

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근 방법

머리 꼬리를 보고 연결리스트로 구현해야겠다는 생각이 들었다. 

그 과정에서 경우를 나누어서 생각해 보았다.

 

뱀이 사과를 먹지 않은 경우

이 경우에는 뱀 머리의 위치를 추가해준 뒤 뱀 꼬리의 위치를 추가해준다.

그 후 뱀의 꼬리 위치를 삭제 해준다.

 

뱀이 사과를 먹은 경우

이 경우에는 뱀 머리의 위치를 추가한 뒤 뱀 꼬리의 위치를 추가해준다.

그 후 뱀의 꼬리 위치를 삭제하지 않는다.

 

뱀이 보드판에서 나간 경우

이 경우에는 카운트를 멈추어 준다,

 

뱀이 자기 몸통에 충돌한 경우

이 경우에는 뱀의 위치가 중복된다는 것과 같다 따라서 리스트의 뱀위치 값을 중복검사를 통해 카운트를 멈추어 준다.

 

코드 구현 

나는 c++로 구현을 해보았다.

#pragma warning(disable: 4996)
#include <iostream>
#include <list>
#include <set>
#include <iterator>
class Direct {
public:
	int time;
	char direct;

	Direct(int t, char d) {
		this->time = t;
		this->direct = d;
	}
	Direct() {                                                                                                                      // 위에 생성자를 만들어서 기본 생성자를 만들어주어야 함
	};
};

class Point {
public:
	int x, y;
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	Point() {};
};


using namespace std;
Point SnakeHeading(Point cur, char direct) {
	if (direct == 'D') {
		if (cur.x == 1 && cur.y == 0) {
			return Point(0, 1);
		}
		else if (cur.x == -1 && cur.y == 0) {
			return Point(0, -1);
		}
		else if (cur.x == 0 && cur.y == -1) {
			return Point(1, 0);
		}
		else if (cur.x == 0 && cur.y == 1) {
			return Point(-1, 0);
		}
	}
	else {
		if (cur.x == 1 && cur.y == 0) {
			return Point(0, -1);
		}
		else if (cur.x == -1 && cur.y == 0) {
			return Point(0, 1);
		}
		else if (cur.x == 0 && cur.y == -1) {
			return Point(-1, 0);
		}
		else if (cur.x == 0 && cur.y == 1) {
			return Point(1, 0);
		}
	}
}
int main() {
	using namespace std;
	
	int N, K, time, row, column, i, j, numDirection, countq, directcnt=0;
	char direction;  // 문자형 방향 돌리기
	set<pair<int, int>> copysnake;
	
	list<Point> snakeList;
	snakeList.push_back(Point(1, 1));

	Point curSnakedirect = Point(1, 0); // 뱀의 방향
	Point curSnakePosition = Point(1, 1); //뱀의 위치
	list<Point>::iterator it;


	scanf("%d", &N);
	scanf("%d", &K);
	int** Board = new int*[N+1];
	for (i = 0; i <= N; i++) {
		Board[i] = new int[N+1];
	}
	for (i = 0; i <= N; i++) {
		for (j = 0; j <= N; j++) {
			Board[i][j] = 0; //보드판
		}
	}

	for ( i = 0; i < K; i++) {
		scanf("%d %d", &row, &column);
		Board[row][column] = 1;
	}
	
	scanf("%d", &numDirection);
	Direct* directionList = new Direct[1004];
	for (i = 0; i < numDirection; i++) {
		scanf("%d %c", &time, &direction);
		directionList[i] = Direct(time, direction);                 
	}
	for (countq = 1; ; countq++) {
		curSnakePosition.x += curSnakedirect.x;
		curSnakePosition.y += curSnakedirect.y; 
		if (curSnakePosition.x > N || curSnakePosition.y > N || curSnakePosition.y <= 0 || curSnakePosition.x <= 0) // 탈출조건
			break;

		snakeList.push_back(Point(curSnakePosition.x, curSnakePosition.y));  //머리추가
	
		for (it = snakeList.begin(); it != snakeList.end(); ++it) {
	
			copysnake.insert({ it->x, it->y });
		}
		if (copysnake.size() != snakeList.size()) {   //중복값있을 경우 탈출
			break;
		}

		copysnake.clear();
		
		if (Board[curSnakePosition.y][curSnakePosition.x] == 0) 
			snakeList.pop_front();  //꼬리제거
		else{
			Board[curSnakePosition.y][curSnakePosition.x] = 0; 
		}

		if (countq == directionList[directcnt].time) {
			curSnakedirect = SnakeHeading(curSnakedirect, directionList[directcnt].direct); //뱀의 방향 바꾸기

			if(directcnt <numDirection)
			    directcnt++;
		}
	}

	cout <<countq;



}

 

구현 시 까다로웠던 점

카운트가 지났을 때 순서가 헷갈릴 수 있으니 주의하면 좋을 것 같다

-> 뱀의 머리 이동 -> 머리위치 리스트에 넣기 -> 위치 중복 확인 -> 사과여부에 따른 꼬리 위치 삭제 여부 -> 시간 별 뱀의 방향 확인 및 조정

 

뱀이 사과를 먹을 경우 사과를 제거해 주어야 한다는 점을 문제 조건에서 잘 확인하지 못해 헤멨다

 

기존 뱀리스트를 set으로 중복없는 리스트를 만들어 둘의 사이즈를 비교하는 식으로 중복체크를 구현했다.

그 과정에서 set에 내가 구현한 클래스를 넣어주면  set라이브러리에서는 그것을 알지 못한다 

따라서 나는 set<pair<int, int>> copysnake이런식으로 페어set을 구현해 직접 두개의 int값을 넣어 주었다.

 

구현하는 중간에 assertion failed라는 오류가 발생했었는데 인덱스의 범위를 넘어서서 배열에 접근할 경우 생기는 오류로

범위 수정을 해주었더니 바로 해결 되었다.