[백준 15685번 드래곤 커브] C++

[15685번]
https://www.acmicpc.net/problem/15685

새로 찍히는 점을 기준으로 지금까지 저장했던 방향을 역순으로 돌면서 새로운 점을 찍어주면 되는 간단한 문제였다.
필자는 초반에 좌표를 저장해서 찍어야하는 문제로 풀이 방향을 잡아나갔으나 구현이 녹록치 않아 다른 방법을 생각해 본 결과 방향을 이용하면 풀린다는 결론을 얻었다(1시간 반 정도 쓴 것 같다).

풀이 방법

1.

2차원 배열 map[101][101]을 생성하고 제일 처음 주어지는 x,y의 값과 방향 d로 두 개의 점을 먼저 찍는다. 두 번째로 찍은 점은 nx,ny로 저장한다.

vector<int> dirs를 생성하고, 주어진 방향 d를 넣는다.

2.

2중 for문으로 g만큼 순회하며 dirs에 넣은 방향을 역순으로 d를 꺼내 90도 회전시킨 새로운 방향 nd를 얻고,
nx,ny를 nd를 통해 갱신하고 새로 map에 찍어준다. 이제 nd를 dirs에 새로 추가한다.

3.

점을 다 찍었다면 main 메서드에서 네 꼭지점의 값이 모두 1인 정사각형 칸의 세어주면 된다. 맨 마지막 행과 열의 index를 빼고 i,j가 0부터 99까지만 값을 갖도록 2중 for문으로 세어준다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int map[101][101];
int N;
int x,y,d,g;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};


void move(int x, int y, int d, int g) {

	vector<int> dirs;
	dirs.push_back(d);
	

	map[y][x] = 1;
	int ny=y+dy[d], nx=x+dx[d];

	map[ny][nx] = 1;

	for(int k=0;k<g;++k) {
		for(int i=dirs.size()-1;i>=0;--i) {
			int nd = (dirs[i]+1) % 4;
			ny = ny+dy[nd];
			nx = nx+dx[nd];

			map[ny][nx] = 1;
			dirs.push_back(nd);
		}
	}

}


int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d", &N);

	for(int i=0;i<N;++i) {
		scanf("%d%d%d%d", &x, &y, &d, &g);
		move(x,y,d,g);
	}

	for(int i=0;i<100;++i) {
		for(int j=0;j<100;++j) {
			if(map[i][j]==1 && map[i][j+1]==1 && map[i+1][j]==1 && map[i+1][j+1]==1) {
				ans++;
			}
		}
	}

	printf("%d\n", ans);
	
	return 0;
}

실행결과