백준 15685 드래곤커브

 

15685번: 드래곤 커브

설계

드래곤커브 그리기

현재 끝 점(문제 본문 참조)으로부터 드래곤 커브 연장시켜 다음 끝 점까지 이어간다. 드래곤 커브를 연장시키는 방법은 이때까지 지나온 방향을 역순으로 순회하되, 각 방향을 반시계방향으로 90도 회전한다. 이를 코드로 나타내면 다음과 같다:

vector<int> 누적진행방향;		// 현재까지 진행 방향
int 90도회전[] = {1, 2, 3, 0};		// 인덱스 방향을 반시계 방향으로 회전한 방향
...
plot(int r, int c, int d){	// 점 (r, c)를 방문표시(누적진행방향에 push), 방향 d에 따라 다음 좌표로 갱신
...
for(auto it = 누적진행방향.rbegin(); it != 누적진행방향.rend(); ++it){	// 현재까지 진행방향을 역순으로 순회
	plot(r, c, 90도회전[*it]);	// 반시계 90도 회전한 방향으로 드래곤 커브를 이어나간다.
}

정사각형의 개수 산출

특정 점을 방문하면 좌표상에 방문 여부를 표시함과 더불어 인접한 4개의 정사각형 각각에 방문된 점 개수를 증가시킨다. 방문된 점 개수가 4개가 되면 정사각형의 개수를 증가시킨다. 드래곤 커브가 겹칠 수 있지만 방문 처리는 단 한번만 해야함으로 주의한다.

bool 좌표방문[101][101];		// 0 <= x <= 100, 0 <= y <= 100
int 정사각형방문[100][100];	// 점 4개 사이에 정사각형 하나 존재 -> 좌표상에 총 99 * 99개의 정사각형이 존재
...
plot(int r, int c, int d){	// 점 (r, c)를 방문표시(누적진행방향에 push), 방향 d에 따라 다음 좌표로 갱신
    if(!좌표방문[r][c]){	// 처음 방문한 점의 경우에만 방문 처리
    	좌표방문[r][c] = 1;	// 좌표상 방문처리
        for((nr, nc)은 r과 c와 인접한 정사각형의 좌표){
        	if(++sq[nr][nc] == 4){	// 해당 정사각형의 모든 점이 방문되었으면 
            	++정답;				// 정사각형 개수를 증가
            }
        }
    }
    ...
    cout << 정답;
    return 0;
}

디버깅

• 문제 파악 미흡
  • 주어진 방향 인덱스가 오름차순 반시계방향으로 회전한다.
  • x, y가 100이하이므로 100이 될 수 있다.
• loop의 탈출조건에 container의 실시간 크기를 사용할 경우 loop body에서 container에 삽입, 삭제 연산을 수행하지 않도록 한다.
• 처음 방문한 경우에만 방문처리할 것

코드

#include <iostream>
#include <vector>
using namespace std;
int N, r, c, d, g;
bool vst[101][101];
int sq[100][100];
vector<int> v;
int ans;
int dr[] = { 0, -1, 0, 1 };
int dc[] = { 1, 0, -1, 0 };
int adjr[] = { -1, -1, 0, 0 };
int adjc[] = { -1, 0, -1, 0 };
int nd[] = { 1, 2, 3, 0 };
void plot(int &r, int &c, int d) {
	if (!vst[r][c]) {
		vst[r][c] = 1;
		for (int i = 0; i < 4; ++i) {
			int nr = r + adjr[i], nc = c + adjc[i];
			if (nr < 0 || 99 < nr || nc < 0 || 99 < nc) {
				continue;
			}
			if (++sq[nr][nc] == 4) {
				++ans;
			}
		}
	}
	v.push_back(d);
	r += dr[d], c += dc[d];
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	while (N--) {
		v.clear();
		cin >> c >> r >> d >> g;
		plot(r, c, d);
		while (g--) {
			int vs = v.size();
			for (int i = vs - 1; i >= 0; --i) {
				plot(r, c, nd[v[i]]);
			}
		}
		plot(r, c, 0);
	}
	cout << ans;
	return 0;
}