백준3190(뱀)

jh Seo·2022년 10월 21일
List백준한번에 못 푼 문제
1

백준

목록 보기
57/194
post-custom-banner

개요

백준3190번: 뱀

  • 입력
    첫째 줄에 보드의 크기 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가 증가하는 순으로 주어진다.

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

접근 방식

1. 뱀을 연결리스트로 구현했다. 대신 head 노드부분이 뱀의 머리를 가리키고 tail노드 부분이 뱀의 꼬리를

가리키도록 만들었다.

2. 간략한 함수 설명

bool checkIfApple(int x, int y)

위 함수에서 x행 y열에 사과가 있는지 체크하는 역할이고,

bool EatApple(int x,int y)

위 함수는 리스트를 구현한 Snake클래스의 멤버함수로 x행 y열 칸에 사과가 존재할 때, 뱀 머리를 새로 생성하고 꼬리를 자르는 함수다.

bool NoApple(int x, int y)

위 함수는 리스트를 구현한 Snake클래스의 멤버함수로 x행 y열 칸에 사과가 존재하지 않을 때, 뱀 머리를 새로 생성하는 함수다.

bool moveSnake(int index)

위 함수는 위의 작성한 함수들을 사용해 뱀을 움직이는 함수다.

3. 반례들

처음에 검색하지않고 반례를 생각해봤지만 도저히 틀린 이유를 몰랐다.

https://www.acmicpc.net/board/view/56469
뱀 문제 반례모음입니다

질문 검색 게시판에서 이 분의 글을 보고 내 실수들을 깨달았다.

실수들을 보면 사소했던 것인데,

  • x행 y열 칸에 뱀에 몸통이 위치하는지 찾는 함수에서

    bool Find(int x, int y) {
	Node* tmp = tail->next;
	while (tmp != head) {
		if (tmp->x == x && tmp->y == y) {
			return true;
		}
		else
			return false;
	}
}

    이런 식으로 tmp=tmp->next의 문구를 빼먹어서 모든 몸통을 탐색하는게 아니라
    꼬리부분만 비교하고 있었다.

  • 문제를 제대로 안 읽은 부분인데, 사과가 없는 칸에서 머리가 이전 꼬리부분에 닿으면
    당연히 꼬리가 사라지며 충돌이 안나는 줄 알았다.
    -> 문제를 보면
    ["먼저" 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. ]
    라고 정의 되어 있다.
    따라서 꼬리가 사라지는거보다 머리 늘리는게 우선이여서 충돌이 나고 게임 오버가된다.

  • 이 실수도 문제를 제대로 안 읽어서 생긴 것인데,
    사과를 먹으면 해당 칸의 사과를 지워야 한다.
    지우는 부분을 깜박 했다면 다시 해당칸에 도착했을 때 이미 먹은 사과가 남아있어서 계속 길어진다.

    코드

#include<iostream>
#include<vector>

//사실 그냥 모든 점들을 다 움직인다고 생각했는데 매우 비효율적이네 첫값 끝값만 변경해주면 되네 
using namespace std;

int N,K,L,Ans=0;
//사과 위치들
vector<pair<int,int>> appleLoc;
//뱀 움직임 
vector<pair<int, char>> snakeMove;

//뱀의 각 파트
struct Node {
	int x;
	int y;
	Node* next;
	Node* prev;
};

class Snake {
private:
	char dir;
	int size;
	Node* head;
	Node* tail;
public:
	//생성자
	Snake() {
		size = 1;
		dir = 'R';
		head = new Node;
		tail = new Node;
		//맨처음 뱀 녀석
		Node* firstSnake = new Node;
		firstSnake->x = 1;
		firstSnake->y = 1;
		firstSnake->next = head;
		firstSnake->prev = tail;
		head->prev = firstSnake;
		head->next = head;
		tail->next = firstSnake;
		tail->prev = tail;
	}
	//소멸자
	~Snake() {
		Node* tmp1 = tail; 
		Node* tmp2 = new Node;
		while (tmp1 != head) {
			tmp2 = tmp1;
			tmp1 = tmp1->next;
			delete tmp2;
		}
		delete tmp1;
	}
	/// <summary>
	/// 움직인 칸에 사과있을 때
	/// </summary>
	/// <param name="움직인 칸의 x(행)"></param>
	/// <param name="움직인 칸의 y(열)"></param>
	bool EatApple(int x,int y) {
		//범위 벗어나면 벽 부딪힌것 이므로 false
		if (x > N || y > N || x==0 || y==0) return false;
		//스네이크 몸통중에 (x,y)값이 있으면  false
		if (Find(x, y)) return false;
		Node* newHead = new Node;
		newHead->x = x;
		newHead->y = y;
		head->prev->next = newHead;
		newHead->prev = head->prev;
		newHead->next = head;
		head->prev = newHead;
		size++;
		return true;
	}
	/// <summary>
	/// 움직였을때 사과가 아닐때
	/// </summary>
	/// <param name="움직인 칸의 x(행)"></param>
    /// <param name="움직인 칸의 y(열)"></param>
    bool NoApple(int x, int y) {
	//범위 벗어나면 벽 부딪힌것 이므로 false
	if (x > N || y > N || x==0 || y==0) return false;
	//스네이크 몸통중에 (x,y)값이 있으면  false
	if (Find(x, y)) {
		////만약 x,y가 꼬리값이라면 어차피 잘리기 때문에 상관없다 -> 예제 3보니 그건 아닌듯
		//if (tail->next->x == x && tail->next->y == y) {}
		//꼬리값 아니면 return false
		return false;
	}
	//head 새로생성
	Node* newHead = new Node;
	newHead->x = x;
	newHead->y = y;
	head->prev->next = newHead;
	newHead->prev = head->prev;
	newHead->next = head;
	head->prev = newHead;

	//tail 가리키는 값 지우기
	Node* tmp = tail->next;
	tail->next = tmp->next;
	tmp->next->prev = tail;
	delete tmp;

	return true;
}
/// <summary>
/// x행 y열에 노드가 있는지 찾는 함수 
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
bool Find(int x, int y) {
	Node* tmp = tail->next;
	while (tmp != head) {
		if (tmp->x == x && tmp->y == y) {
			return true;
		}
		else
			tmp = tmp->next;
	}
	return false;
}


//방향 프로퍼티 함수
char GetDir() { return dir; }
void SetDir(char input) { dir = input; }

//head노드 return하는 함수
Node* Head() { return head; }

};

Snake* s;

/// <summary>
/// x행 y열에 사과 잇는지 체크
/// </summary>
/// <param name="x행"></param>
/// <param name="y열"></param>
/// <returns>사과 있다면 true, 없으면 false</returns>
bool checkIfApple(int x, int y) {


	////임시방편으로 짠거 이런식으로하면 지워져도 0,0과 계속 비교하게 되서 비효율적
	//for (int i = 0; i < K; i++) {
	//	if (x == appleLoc[i].first && y == appleLoc[i].second) {
	//		appleLoc[i].first = 0;
	//		appleLoc[i].second = 0;
	//		return true;
	//	}
	//}
	//return false;

	//erase로 좀더 효율적으로
	for (auto iter = appleLoc.begin(); iter != appleLoc.end(); ++iter) {
		if (iter->first == x && iter->second == y) {
			appleLoc.erase(iter);
			return true;
		}
		
	}
	return false;
}

void input() {
	int appleX = 0, appleY = 0, sec = 0;
	char dir = ' ';
	cin >> N;
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> appleY >> appleX;
		appleLoc.push_back(make_pair(appleY, appleX));
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> sec >> dir;
		snakeMove.push_back(make_pair(sec, dir));
	}
}

/// <summary>
/// index번째 입력값을 가지고 적힌 초만큼 이동하고, 적힌 방향으로 방향 전환함
/// </summary>
/// <param name="index"></param>
/// <returns>이동할 수 없다면 false, 이동을 완료했다면 true</returns>
bool moveSnake(int index) {
	//첫번째 인덱스일땐 index-1하면 음수값 index접근하므로 오류나므로
	if (index == 0) {
		for (int i = 0; i < snakeMove[index].first; i++) {
			//방향은 무조건 오른쪽
			//오른쪽에 사과가 있다면
			if (checkIfApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
				//오른쪽으로 성공적으로 이동했다면
				if (s->EatApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
			//사과 없다면
			else {
				//오른쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
		}
		if (snakeMove[index].second == 'L')
			//이동 다 했다면 dir값 변경해준 후 true 리턴
			s->SetDir('U');
		else
			s->SetDir('D');
		return true;
	}
	//마지막 인덱스값까지 벽이나 몸통에 안 부딪혔다면
	if (index == L) {
		if (s->GetDir() == 'U') {
			while (1) {
				//위쪽에 사과가 있다면
				if (checkIfApple(s->Head()->prev->x - 1, s->Head()->prev->y)) {
					//위쪽으로 성공적으로 이동했다면
					if (s->EatApple(s->Head()->prev->x - 1, s->Head()->prev->y)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
				//사과 없다면
				else {
					//위쪽으로 성공적으로 이동했다면
					if (s->NoApple(s->Head()->prev->x - 1, s->Head()->prev->y)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
			}

		}
		else if (s->GetDir() == 'D') {
			while (1) {
				//아래쪽에 사과가 있다면
				if (checkIfApple(s->Head()->prev->x + 1, s->Head()->prev->y)) {
					//아래쪽으로 성공적으로 이동했다면
					if (s->EatApple(s->Head()->prev->x + 1, s->Head()->prev->y)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
				//사과 없다면
				else {
					//아래쪽으로 성공적으로 이동했다면
					if (s->NoApple(s->Head()->prev->x + 1, s->Head()->prev->y)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
			}
		}
		else if (s->GetDir() == 'L') {
			while (1) {
				//왼쪽에 사과가 있다면
				if (checkIfApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
					//왼쪽으로 성공적으로 이동했다면
					if (s->EatApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
				//사과 없다면
				else {
					//왼쪽으로 성공적으로 이동했다면
					if (s->NoApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
			}
		}
		else if (s->GetDir() == 'R') {
			while (1) {
				//오른쪽에 사과가 있다면
				if (checkIfApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//오른쪽으로 성공적으로 이동했다면
					if (s->EatApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
						//답 ++
						Ans++;
					}
					//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
					else {
						Ans++;
						return false;
					}
				}
				//사과 없다면
				else {
				//오른쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
				}
			}
		}
		return true;
	}
	//지금 방향 왼쪽이라면
	if (s->GetDir() == 'L') {
		//해당 초만큼 왼쪽으로 움직임 
		for (int i = snakeMove[index-1].first; i < snakeMove[index].first; i++) {
			//왼쪽에 사과가 있다면
			if (checkIfApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
				//왼쪽으로 성공적으로 이동했다면
				if (s->EatApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
			//사과 없다면
			else {
				//왼쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x, s->Head()->prev->y - 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
		}
		if (snakeMove[index].second == 'L')
			//이동 다 했다면 dir값 변경해준 후 true 리턴
			s->SetDir('D');
		else
			s->SetDir('U');
		return true;

	}
	else if (s->GetDir() == 'R') {
		//해당 초만큼 오른쪽으로 움직임 
		for (int i = snakeMove[index - 1].first; i < snakeMove[index].first; i++) {

			//오른쪽에 사과가 있다면
			if (checkIfApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
				//오른쪽으로 성공적으로 이동했다면
				if (s->EatApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
			//사과 없다면
			else {
				//오른쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x, s->Head()->prev->y + 1)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
		}
		if (snakeMove[index].second == 'L')
			//이동 다 했다면 dir값 변경해준 후 true 리턴
			s->SetDir('U');
		else
			s->SetDir('D');
		return true;
	}
	else if (s->GetDir() == 'U') {
		//해당 초만큼 위쪽으로 움직임 
		for (int i = snakeMove[index - 1].first; i < snakeMove[index].first; i++) {

			//위쪽에 사과가 있다면
			if (checkIfApple(s->Head()->prev->x-1, s->Head()->prev->y)) {
				//위쪽으로 성공적으로 이동했다면
				if (s->EatApple(s->Head()->prev->x-1, s->Head()->prev->y)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
			//사과 없다면
			else {
				//위쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x - 1, s->Head()->prev->y)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
		}
		if (snakeMove[index].second == 'L')
			//이동 다 했다면 dir값 변경해준 후 true 리턴
			s->SetDir('L');
		else
			s->SetDir('R');
		return true;

	}
	else if (s->GetDir() == 'D') {
		//해당 초만큼 아래쪽으로 움직임 
		for (int i = snakeMove[index - 1].first; i < snakeMove[index].first; i++) {

			//아래쪽에 사과가 있다면
			if (checkIfApple(s->Head()->prev->x+1, s->Head()->prev->y )) {
				//아래쪽으로 성공적으로 이동했다면
				if (s->EatApple(s->Head()->prev->x+1, s->Head()->prev->y )) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
			//사과 없다면
			else {
				//아래쪽으로 성공적으로 이동했다면
				if (s->NoApple(s->Head()->prev->x + 1, s->Head()->prev->y)) {
					//답 ++
					Ans++;
				}
				//이동못하면 벽에막히거나 자기 몸에 막힌것이므로 false 리턴
				else {
					Ans++;
					return false;
				}
			}
		}
		if (snakeMove[index].second == 'L')
			//이동 다 했다면 dir값 변경해준 후 true 리턴
			s->SetDir('R');
		else
			s->SetDir('L');
		return true;

	}

	return true;
}

void solution() {
	for (int i = 0; i < L; i++) {
		if (!moveSnake(i))
		{
			cout << Ans;
			return;
		}

	}
	moveSnake(L);
	cout << Ans;
}

int main() {
	s = new Snake();
	input();
	solution();
	delete s;
}

문풀후생

문제를 잘 읽고 조건을 파악하는 게 제일 중요하다.
아무리 예제 통과해봤자 결국 나중에 문제 풀때는 내가 반례를 스스로 생각해서
어떤 조건이 있는지를 알아내야하기 때문이다.
끝 값 반례나 공간,시간복잡도 생각보다 먼저 문제 조건부터 꼼꼼히 체크해야겠다는 생각이 들었다.

멤버 함수 구현하다가 기초개념이 부족해서 매개 변수의 디폴트값을 멤버 변수로 정했더니

"비정적 멤버 참조는 특정 개체에 상대적이어야 합니다"

이런 오류가 떴다.
아직 변수의 기초개념을 제대로 정립 못한 것 같아서 공부를 다시 했다

[링크]

profile
jh Seo
코딩 창고!
이전 포스트

백준5397(키로거)

다음 포스트

백준 10828(스택)

post-custom-banner

1개의 댓글

comment-user-thumbnail
Yeunseo Oh
2022년 11월 13일

코드가 뱀이다
뱀같이 길다
🐍🐍🐍🐍🐍🐍🐍

답글 달기