백준 15685. 드래곤 커브

문제출처 : baekjoon online judge

15685번: 드래곤 커브

이 문제는 스택을 활용한 문제입니다.

0세대일 때의 두 점을 우선 1로 표현하고 방향을 스택에 저장합니다.

그 후, 스택의 방향을 pop하여 다음 방향을 구하고 다시 그 방향을 스택에 push하는 방식으로 문제를 해결합니다. 실제로 pop을 하지는 않고 다른 변수에 저장해서 활용합니다.

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dir_x[4] = { 1,0,-1,0 };
int dir_y[4] = { 0,-1,0,1 };
 
int next_dir[4] = { 1,2,3,0 };
int stack_dir[1024];
int dir_top = 0;
 
int map[102][102];
 
int count(int x1, int y1, int x2, int y2) { // 네모 개수 세기
    int sum = 0;
 
    for (int i = y1; i < y2; i++) {
        for (int j = x1; j < x2; j++) {
            if (map[i][j] == 1 && map[i + 1][j + 1] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1) 
                sum++;
        }
    }
 
    return sum;
}
int main() {
    int n;
 
    cin >> n;
 
    int min_x = 101, min_y = 101, max_x = -1, max_y = -1; // 탐색해야될 범위를 저장
 
    for (int i = 0; i < n; i++) {
        int x, y, d, g;
 
        cin >> x >> y >> d >> g;
 
        min_x = min(x, min_x);
        min_y = min(y, min_y);
        max_x = max(x, max_x);
        max_y = max(y, max_y);
 
        map[y][x] = 1; // 첫번째 점
 
        stack_dir[dir_top++] = d;
 
        x = x + dir_x[d];
        y = y + dir_y[d];
 
        min_x = min(x, min_x);
        min_y = min(y, min_y);
        max_x = max(x, max_x);
        max_y = max(y, max_y);
 
        map[y][x] = 1; // 두번째 점
        
        for (int i = 0; i < g; i++) {
            int tmp = dir_top - 1;
            for (int j = tmp; j >= 0; j--) {
                d = next_dir[stack_dir[j]]; // pop
 
                x = x + dir_x[d];
                y = y + dir_y[d];
 
                min_x = min(x, min_x);
                min_y = min(y, min_y);
                max_x = max(x, max_x);
                max_y = max(y, max_y);
 
                map[y][x] = 1;
 
                stack_dir[dir_top++] = d; // push
            }
        }
        dir_top = 0;
    }
    int result = count(min_x, min_y, max_x, max_y);
 
    cout << result << endl;
}

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!