[성실코딩 24일차] 백준 #15685 드래곤 커브

이런게 시뮬레이션 문제인가?

나는 시뮬레이션 문제는 잘 못하고 안좋아한다고 생각했는데 재밌게 풀었다!!!!!!!!

안해봐서 그런거엿나 ㅎㅎㅎ

알고리즘

회전해야하는 점과 끝점의 위치관계를 확인한다. 

1) 끝점.x == 회점.x && 끝점.y < 회점.y

2) 끝점.x == 회점.x && 끝점.y > 회점.y

3) 끝점.x > 회점.x && 끝점.y == 회점.y

4) 끝점.x < 회점.x && 끝점.y == 회점.y

네 가지 경우가 가능하고, 각 경우에 따라 90도 회전해서 놓여지는 점의 좌표가 달라진다.

그리고 여기서 끝점이란, 현재 점 다음으로 들어온 점을 가리키는 것이다.

나는 stack에 넣어가면서 

top-1 ~ 0까지 하나씩 확인하며 회전시켰다.

index 와 index+1을 비교하며 회전 방향을 정해줌.

회전방향을 정해주고 실제 좌표값 결정은 top기준으로 한다. 

그리고 결정된 새로운 좌표는 또 stack에 push한다.

(내가 봐도 설명을 잘못하는 것 같다,,,,)

구현 코드

#include < iostream >
#include < vector >

#define SZ 101

using namespace std;

int visited[SZ][SZ] = { 0, };
int dr[3] = {0,1,1}; // 우, 우하, 하
int dc[3] = {1,1,0};

int main() {

	int tc;
	// 입력
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;  // 입력받기
		
		vector< pair< int, int >> s;  // 스택 매번 초기화
		s.push_back(make_pair(x,y));	 // push
		visited[x][y] = 1;  // 방문 표시
		switch (d)
		{
		case 0:   // ->
			x = x + 1;
			break;
		case 1:  // 위
			y = y - 1;
			break;
		case 2:  // <-
			x = x - 1;
			break;
		case 3:  // 아래
			y = y + 1;
			break;
		}
		s.push_back(make_pair(x, y));
		visited[x][y] = 1;


		// g 세대
		for (int j = 0; j < g; j++) {
			// stack 사이즈만큼 반복
			int cnt = s.size()-2; // 가장 위(top)은 빼고
			for (int k = cnt; k > -1; k--) {
				
				int reference_x = s[k + 1].first;
				int reference_y = s[k + 1].second;
				int new_x = s[k].first;
				int new_y = s[k].second;

				// 4가지 경우
				if (reference_x == new_x) {
					if (reference_y < new_y) {
						new_x = s.back().first-1;
						new_y = s.back().second;
					}
					else {  // reference_y > new_y
						new_x = s.back().first + 1;
						new_y = s.back().second;
					}
				}
				else if(reference_y == new_y){
					if (reference_x > new_x) {
						new_x = s.back().first;
						new_y = s.back().second - 1;
					}
					else {
						new_x = s.back().first;
						new_y = s.back().second + 1;
					}
				}
				s.push_back(make_pair(new_x, new_y));
				visited[new_x][new_y] = 1;
			}
		}
	}
	// 네 꼭지점이 모두 드래곤 커브인 것 갯수 세기
	int ans = 0;
	for (int r = 0; r < SZ-1; r++) {
		for (int c = 0; c < SZ - 1; c++) {
			if (visited[r][c]==1) {
				int k;
				for (k = 0; k < 3; k++) {
					if (visited[r+dr[k]][c+dc[k]]==0) {
						// 하나라도 방문안한게 있다면 break
						// break하면 가장 가까운 for문 k=3을 벗어난다.
						break;
					}
				}
				if (k==3) {
					// k==3이라면,
					// for 3번을 모두 다 돌은 것이다
					// 즉, 모두 1임!
					ans++;
				}
			}
		}
	}

	cout << ans<< endl;

	return 0;
}