[백준OJ] 3190번 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

---

-풀이-

maze[101][101] 배열을 선언해준다. 0=빈칸, -1=뱀 , 1=사과 로 설정해뒀다.

change_time[10001][2]도 선언을 해주는데, 이것은 매 루틴이 끝날때, 끝나는 시각t에 L이나 D의 명령어가 있으면 방향을 바꿀때 필요한 배열이다. change_time[t][k] = t초에 k(LEFT=0, RIGHT=1) 로 바꾸라는 명령

 

1. 사과의 좌표를 입력받아 maze배열에 1로 셋팅시켜준다.

2. 방향이 바뀌는 시간과 해당 방향을 입력받아 change_time에 셋팅해준다.

3. deque에 초기 위치를 push한뒤, 해당 방향으로 전진하며, 사과가 있다면, 꼬리를 pop_back()해줄 필요가 없으니 건너뜀

4. 하지만 사과가 없다면 꼬리를 잘라야 하니까 pop_back();

5. 전진한 칸을 -1로 업데이트

6. 시간을 증가시켜준 뒤, 해당시간에 방향을 바꾼다면 방향을 바꿔줌.

방향을 바꿀때, 현재 진행하고있는 방향을 위의 그림과 같이 바꿔주면된다.

초기 방향이 1(x축으로 0, y축으로 1) 만큼 움직이는건데, 왼쪽으로 방향을 틀면 순서대로 (0,1)->(-1,0)->(0,-1)->(1,0)->(0,1)이런식으로 돌아가고, 오른쪽으로 방향을 틀면 반대순서로 돌아간다.

따라서 L명령어면 현재진행방향 d=(d+1)%4; 를 해주면되고, R명령어면 현재진행방향 d==0?d=3 ? d--; 를 해준다.

 

7.만약 다음 진행할 부분이 뱀( -1 ) 이거나 ,범위 밖이면 종료하고 time을 출력해준다.

 

-시간복잡도-

t의 최댓값 10000초까지 살아서 10000초에서 방향을 바꾸고, 이때 제일 모서리에 있으면, 10000+n초 뒤에 게임이 종료되는것이 최악의 상황이다. n은 100이하이기 때문에 O(t+n)이 된다. (t는 방향정보에서 가장 마지막에받는 시간)

 

-코드-

 

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

int n, k, l;
int maze[101][101] = { 0 };
int mv[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };
bool change_time[10001][2] = { 0 };//left=0, right=1;
deque<pair<int, int>> snake;

bool isIn(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main(){
	cin >> n;
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		maze[x][y] = 1;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		int time;
		char direct;
		cin >> time >> direct;
		change_time[time][direct == 'L' ? 0 : 1] = true;
	}

	int time = 0;
	int d = 0;
	maze[1][1] = -1;
	snake.push_back({ 1,1 });
	while (true) {
		int nowx = snake.front().first;
		int nowy = snake.front().second;

		int nextx = nowx + mv[d][0];
		int nexty = nowy + mv[d][1];

		if (maze[nextx][nexty] == -1||!isIn(nextx,nexty)) {
			time++;
			break;
		}

		if (maze[nextx][nexty] == 0) {
			int tailx = snake.back().first;
			int taily = snake.back().second;
			maze[tailx][taily] = 0;
			snake.pop_back();
		}
		maze[nextx][nexty] = -1;
		snake.push_front({ nextx,nexty });
		time++;

		if (change_time[time][0] || change_time[time][1]) {
			if (change_time[time][0]) {
				d=(d+1)%4;
			}
			else {
				d == 0 ? d = 3 : d--;
			}
		}
	}
	cout << time <<"\n";
}