[백준] 3190_뱀_C++ 삼성 SW역량테스트 기출

삼성 기출문제인 뱀입니다.

www.acmicpc.net/problem/3190

3190번: 뱀

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int map[101][101];
int n, k, l, t;
int now_d = 1;
deque<pair<int, int>> snake;
vector<pair<int, char>>v;
//상우하좌
int dx[4] = { -1, 0, +1, 0 };
int dy[4] = { 0, +1, 0, -1 };
bool getAns;

bool canMove() {
	int x = snake.front().first;
	int y = snake.front().second;
	int nx = x + dx[now_d];
	int ny = y + dy[now_d];
	if (map[nx][ny] == -1 || nx < 1 || nx > n || ny < 1 || ny > n) {
		return false;
	}
	
	if (map[nx][ny] == 0) {//사과가 없다면
		int bx = snake.back().first;
		int by = snake.back().second;
		snake.pop_back();
		map[bx][by] = 0; //몸통 제거
	}
    
	snake.push_front({ nx, ny });
	map[nx][ny] = -1; //몸통은 -1로
	return true;
}

int main() {
	snake.push_back({ 1, 1 });
	map[1][1] = -1;
	scanf_s("%d\n%d\n", &n, &k);
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		//사과위치는 1로 해둠
		map[x][y] = 1;
	}
	cin >> l;
	
	for (int i = 0; i < l; i++) {
		int x; char c;
		cin >> x >> c;
		v.push_back({ x,c });
	}
	for (int i = 0; i < l; i++) {
		int x = v[i].first;
		char c = v[i].second;
		while (t < x) {
			if (!canMove()) {
				cout << t + 1;
				return 0;
			}
			t++; 
			//canMove로 미리 이동을 시켜놓은 다음에
			//t++를 하는 거니까 t == x라면 이미 x초까지의 수행이 다 된거야.
		}
		//x초까지 수행하고 그 다음
		if (c == 'D')
			now_d = (now_d + 1) % 4;
		else
			now_d = (now_d + 3) % 4;
 	}
	while (1) {
		if (!canMove()) {
			cout << t + 1;
			return 0;
		}
		t++;
	}
	return 0;
}

 

 

나 혼자만의 끄적끄적임 (왜 오답이었는가에 대해)

 

나는 canMove()에서 다음에 갈 곳에 대해 미리 -1을 해둠으로써 몸통 표시를 해놨었는데,  그 이후에 사과가 있는 지 확인하면서 사과가 있던(1이었던 자리) 곳(앞으로 갈 곳)을 다시 0으로 변경해놨었다... 초기화 한답시고..바보냐 

 

앞으로 갈 곳이 사과가 있든 없든 그 자리는 -1이 되면서 몸통 표시가 되고, 사과 여부에 영향 받는 것은 꼬리이다. 사과가 없으면 현 꼬리를 제거해야하고, 사과가 있다면 꼬리를 제거할 필요가 없다. 즉 꼬리를 제거하느냐 마냐의 문제지 사과를 없앴고 말고 이런 거를 괜히 해서....ㅎㅎㅎㅎ 몸통으로 -1 해둔 곳에 다시 0을 해놓는 대참사 발생했었다...ㅎ

 

그리고 canMove부분에서 while(t<x)인데 t<=x라고 해 둔 부분도 오답이었다. canMove자체가 내가 앞으로 갈 곳에 대한 탐색을 하는 부분이다. 즉 현재 t가 아니라 t+1일때 가는 곳에 대한 탐색 함수이다. 즉, canMove를 true로 통과했다면 이는 t+1에 대한 수행을 모두 마친 것이고 while아래 t++을 거쳐 t를 동기화 시켰기 때문에 t==x라면 x초 까지 수행해야 할 일을 모두 마친 상태인 것이다. t==x라면 회전만 하면 되는 것이다.