백준 15685 드래곤커브

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

15685번: 드래곤 커브

 

- 시간복잡도는 신경 쓸 필요 없는 문제이다. g가 최대 10일때, 2^10 + 2^9 .. 정도의 계산량밖에 되지 않기 때문

 

- 규칙을 찾아내면 된다. 스택2개와 큐 1개를 사용했는데, 더 간단한 방법이 있지 않을까 생각한다.

 

- x,y좌표는 계속해서 최신화하면서, 어느 방향으로 전진해야 하는 지를 구한다. 예를 들어 0과 1을 사용하여 전진을 했다면, 다음 세대에서 사용되는 방향은 2,1이고 1,2,1,0(위에서부터)을 스택에 담아서 다음 세대에서 활용될 수 있도록 해야 한다. 여기서 규칙을 찾는 것이다.

 

  (1) 스택 a에서 한 개의 값을 꺼낸다.

  (2) 90도 회전한 방향을 구해서, 해당 방향으로 x,y를 최신화한다.

  (3) a에서 꺼낸 값은 b스택으로, 회전한 방향은 c 큐로 push한다.

  (4) 위 과정을 a가 빌 때까지 반복한 후, b에있는 모든 것을 a에 push하고 c에 있는 모든 것을 a에 push한다.

  (5) 다음 세대로 넘어가서 이를 반복한다.

 

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
int arr[100][100];
int main() {
	int t;
	cin >> t;
	int answer = 0;
	while (t--) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		arr[x][y] = 1; 
		x += dx[d]; y += dy[d];
		arr[x][y] = 1;
		stack<int> a, b;
		queue<int> c;
		a.push(d);
		while (g--) {
			while (!a.empty()) {
				int temp = a.top(); a.pop();
				b.push(temp);
				int next_d = (temp + 1) % 4;
				x += dx[next_d]; y += dy[next_d];
				arr[x][y] = 1;
				c.push(next_d);
			}
			while (!b.empty()) {
				a.push(b.top()); b.pop();
			}
			while (!c.empty()) {
				a.push(c.front()); c.pop();
			}
		}
	}
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (arr[i][j] && arr[i][j + 1] && arr[i + 1][j] && arr[i + 1][j + 1]) {
				//cout << i << ' ' << j << '\n';
				answer++;
			}
		}
	}
	cout << answer;
	return 0;
}