[삼성코테기출문제] 뱀

뱀

문제

어릴때 게임보이로 많이 해봤던 게임이다! 앞으로 전진하며 좌우로 움직일 수 있고 사과를 먹으면 몸길이가 늘어나고 벽이나 자신의 몸에 부딪히면 끝나는 게임.

문제풀이

뱀이 바라보는 시선을 기준으로 좌우로 움직여야하는데 시선이 바뀔때마다 절대좌표의 증감값이 바뀌는데 이를 해결해주는 부분에서 어려움을 겪었다.
이 문제의 Key Point 는 뱀의 시선에따라 바뀌는 좌우의 방향과 사과를 먹었을 때 늘어나는 몸길이에 대한 처리 방법이었다.

풀이 과정

1. 우선 입력받을때 사과의 위치는 따로 저장하기보다는 바로 맵에 Map[i][j] = 2로 처리해준다. 그리고 L개의 명령을 따로 저장해둔다.
2. 뱀의 시작위치는 항상 (0,0)이므로 큐 에 뱀의 현재 정보를 push해준다. 뱀이 있는 위치 Map[cury][curx] = 1로 표시해주고 현재 뱀의 시선으로 다음 명령이 올 때 까지 전진며 게임시간인 Answer를 증가시켜준다.
3. • 만약 다음 칸이 0 빈칸이면 뱀의 길이는 늘어나지 않으므로 이전 칸은 0 (원래 뱀이 있었으니까 1) 으로 바꿔주고 다음 칸을 1 로 바꿔준다.
   • 만약 다음 칸이 2사과라면 뱀의 길이가 길어져야하므로 이전 칸은 1 로 유지시켜주고, 다음 칸을 1 로 바꿔준다.
   • 그리고 다음 칸을 뱀의 위치로 생각하여 push해준다.
4. 현재 시간인 Answer를 위의 과정을 1번 시행할때마다 명령이 들어있는 d의 시간 과 비교하여 같으면 해당 명령을 실행한다.
   • 이 부분이 관건인데

      int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
      int L[4] = { 3,2,0,1 }, D[4] = { 2,3,1,0 };
      int dir = 0;//뱀의 현재 방향
     

     …생략…

      if (answer == d[dIdx].time) {
        if (d[dIdx].direct == 'L') dir = L[dir];
        else dir = D[dir];
        dIdx++;
      }
     

     왼쪽으로 회전 시킬 때 동쪽이 기준이므로
     북 -> 서 -> 남 -> 동 순으로 사이클이 생긴다.
     dx,dy의 인덱스로 생각해 보면
     0 > 3 > 1 > 2 > 0 이 되고
     오른쪽으로 회전 시킬 때는
     남 -> 서 -> 북 -> 동 순으로 사이클이 생긴다.
     따라서 다음과 같이 방향을 전환해주는 L,D 배열이 필요하다.
     

5. 이 과정을 벽이나 뱀 자신의 몸에 부딪힐 때 까지 반복하면 결과가 나온다.

#include<iostream>

using namespace std;

const int MAX = 100;
int N, K, M; //N: 맵의 크기,  K: 사과의 개수, M: 뱀의 방향 변환 횟수

//우 좌 하 상
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int L[4] = { 3,2,0,1 }, D[4] = { 2,3,1,0 };
int dir = 0;//뱀의 현재 방향

int answer;
int Map[MAX][MAX];

typedef struct DirInfo {
	int time;
	char direct;
}Dir;
Dir d[MAX + 1];
int dIdx;

typedef struct Pos {
	int x, y;
};

Pos Q[MAX*MAX]; int f, r;
void push(int x, int y) {
	Q[r++] = { x,y};
}
Pos pop() {
	return Q[f++];
}
void Input() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		Map[a - 1][b - 1] = 2;	//사과를 2라고 표시
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> d[i].time >> d[i].direct;
	}

}
void Process() {
	Pos cur = { 0,0 };
	Pos next;

	Map[cur.y][cur.x] = 1;
	push(cur.x, cur.y);
	while (1) {
		cur.x += dx[dir];
		cur.y += dy[dir];
		answer++;
		if (cur.y < 0 || cur.x < 0 || cur.x >= N || cur.y >= N||Map[cur.y][cur.x]==1) {
			cout << answer << endl;
			return;
		}
		if (Map[cur.y][cur.x] == 0) {
			next = pop();
			Map[next.y][next.x] = 0;
		}
		Map[cur.y][cur.x] = 1;
		push(cur.x, cur.y);

		if (answer == d[dIdx].time) {
			if (d[dIdx].direct == 'L') dir = L[dir];
			else dir = D[dir];
			dIdx++;
		}
	}
}
void solution() {
	Input();
	Process();
}
int main(){
	freopen("03.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	solution();
	return 0;
}