[ C++/cpp ] 백준 (15685 드래곤 커브) ⭐구현, 시뮬레이션

백준 15685 드래곤 커브

(골드 3)

 

문제링크 https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

 

(정답 코드)

 #include <iostream>
#include <vector>

using namespace std;

const int MAX_SIZE = 100; //맵은 최대 100,100
bool visited [MAX_SIZE+1][MAX_SIZE+1]={false,};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

//드래곤 커브 그려서, 맵에 지나간 꼭짓점 표시
void drowCurve(int x, int y, int d, int g) {
    
    int cur_size=0; //현재의 벡터 사이즈
    int cx=x; //커브의 가장 마지막 점
    int cy=y;
    vector<int> curve;
    visited[y][x]=true;
    curve.push_back(d);
    int tag = 0;
    
    
    
    if(g==0) { //0세대인 경우. 아래의 벡터 조정 필요X.  바로 직선 하나 긋고 종료.
        
        cx+=dx[curve[cur_size]];
        cy+=dy[curve[cur_size]]; //위치 이동!
            
        visited[cy][cx]=true;
        
        return; //종료
    }
    
    while(g--) {
        
        cur_size = curve.size()-1; 
        //벡터에 요소를 넣어서 size가 계속 변하므로, 변수에 미리 지정해두기.
        
        // 해당 세대에 추가된 드래곤 커브의 방향 추가
        for(int i=cur_size; i>=0; i--) { //for문 거꾸로 !!
            curve.push_back((curve[i]+1)%4); 
            // 이전 세대의 마지막 방향부터 +1해서 가장 처음으로 방향 벡터에 넣기
            // k-1 세대의 마지막 직선이 90도 회전해서 k번째 세대의 첫 직선이 되기 때문.
        }
        
        
        if(tag==0) { //가장 처음에만 작동. cur_size번째 벡터도 처음 한 번은 적용해야하므로.
            cx+=dx[curve[cur_size]];
            cy+=dy[curve[cur_size]]; //위치 이동!
            
            visited[cy][cx]=true;
            tag = 1; //tag 변수 켜주기
        }
        
        
        // cur_size+1부터 즉, 이전에 새로 추가된 방향 요소들에 대해, 방문한 꼭짓점 표시
        for(int i=cur_size+1; i<curve.size(); i++) {
            
            cx+=dx[curve[i]];
            cy+=dy[curve[i]]; //위치 이동!
            
            visited[cy][cx]=true;
        }
    }
}

int main()
{
    int n, x, y, d, g;
    int cnt=0; //꼭짓점 모두를 커브가 지나간 1x1 정사각형 개수
    
    cin >> n;


    
    while(n--) {
        cin >> x >> y >> d >> g;
        drowCurve(x,y,d,g);
    }
    
    for(int i=0; i<MAX_SIZE; i++) {
        for(int j=0; j<MAX_SIZE; j++) {
            if(visited[i][j] && visited[i+1][j] && visited[i][j+1] && visited[i+1][j+1]) {
                cnt++; //4꼭짓점이 모두 true이면, 커브가 다 지나간것이므로 cnt++
            }
        }
    }
    
    cout << cnt; //cnt 출력

    return 0;
}

 

주의 ) x,y 좌표계인데 x가 열이고 y가 행이므로 벡터 인덱스를 다룰 때 y,x 순으로 넣어야한다.

처음에 반대로 넣어서 틀림...ㅋㅋ

 

 

 

 

 

📖 풀이 요약

 

도입 

visited : 꼭짓점에 드래곤 커브가 지나쳤는지 T/F 저장하는 이차원 배열

총 100, 100의 좌표계를 가지므로, 101 x 101로 초기화한다.

 

curve는 현재 커브의 방향을 담는 벡터이다.

아래 풀이를 보면 알겠지만, 시계방향으로 전환하는 커브에서

방향이 규칙을 갖기 때문에, 벡터에 추가로 저장해주며 변환을 거쳐야한다.

 

 

방향의 규칙성

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

 

위의 문구를 보고, 많이 그려보며 방향에 규칙이 있다는 것을 알게되었고, 그대로 구현하기만 하면 된다.

 

( 아래의 그림은 나의 풀이를 도식화 한 것이다. 글과 함께 보면 이해가 쉽다. )

 

 

예제 2의 보라색 그래프에서 2세대, 3세대를 보면서 방향의 규칙을 찾아보자.

 

step 1) 방향 전환.

2세대는 끝점을 향해 들어가는 방향, 3세대는 끝점에서 뻗어나가는 방향으로 진행된다.

in 과 out 으로 방향이 정 반대이므로, 먼저 2세대의 방향을 반대로 전환해준다.

기존 방향에 +2를 해야한다.

 

step 2) 시계방향 전환.

2세대의 모양을 그대로 90도 전환해 붙이면, 3세대의 모양이 되므로,

기존 방향을 시계 방향으로 90도 전환해줘야한다.

기존 방향에 -1을 해야한다.

 

위의 과정을 거쳐, 기존 방향에 +1만 해주면 된다는 것을 알 수 있다.

 

 

그리고, 2세대의 마지막 직선이 3세대의 첫 직선이 되는 것을 알 수 있다.

 

풀이 1

 

 

 

 

 

 

자.. 복잡하지만, 침착하고 한 번 더 해보자.

curve 벡터에다가 각 직선들의 방향을 저장한다고 했다.

 

 

2세대에선 curve 벡터에 3, 0, 1, 0이 저장되어 있다.

3세대에선 위에서 찾아낸 규칙에 따라, 1, 2, 1, 0이 추가된다.

 

2세대의 마지막 직선이 3세대의 마지막 직선이 회전한 것이므로,

 

4번째에 담긴 0에 1을 더해 5번째 1을 만들고,

3번째에 담긴 1에 1을 더해 6번째 2를 만들고...

이런 식이다.

 

이때, 방향은 0부터 3까지이므로 %4 mod 연산을 해주어야 한다.

 

 

 

풀이를 찬찬히 이해하고, 위의 코드를 한 번 더 읽어보길 바란다.

골드 3 치고는 쉬웠던 문제같다. 내가 쉽게 풀었으니..^^

 

 

 

 

 

처음으로 푼 골드 3 문제... 뿌듯 :)