[BOJ] 15685. 드래곤 커브

문제 >> [BOJ] 15685. 드래곤 커브

전형적인 시뮬레이션 문제.

방향의 규칙에 대해서 생각해보며 풀었습니다. 

→  ↑ ← ↓  순서로 드래곤커브가 진행된다는 것을 발견하였고, 순서대로 배열에 넣어 인덱스를 활용해 방향을 전환했습니다.

문제에서 주어진 예시를 보면 ,

시작 방향이 오른쪽 일때,

0세대 

 →  

1세대

 →   ↑ 

2세대

 →   ↑ ← ↑

3세대

 →   ↑ ← ↑ ← ↓ ←  ↑

순서로 진행하고 있고, 이들의 규칙은 다음과 같습니다.

1. 이전 세대의 방향들은 LILF로 팝한다.

2. 방향을 회전해서 진행하여 상단에 push하고 원래의 방향을 하단에 add한다.

예시 )

1세대

 →   ↑ 

nowQ : (상) ↑   → (하) 

LILF로 pop

  ↑   회전 후 ==> ← 

(회전된 방향을 상단에 푸시, 원래방향 하단에 애드)

nextQ : (상)   ←  ↑   (하) 

-----------------------------------

nowQ : (상)  → (하) 

LILF로 pop

   →  회전 후 ==> ↑ 

(회전된 방향을 상단에 푸시, 원래방향 하단에 애드)

nextQ : (상)   ↑  ←  ↑ →  (하) 

-----------------------------------

상단부터 팝하면 2세대가 완성되는 것을 확인할 수 있습니다.

2세대

 →   ↑ ← ↑

설명처럼 상단과 하단 모두에 삽입 하기 위해 덱을 사용해 구현했습니다.

<<java>>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
//BOJ :: 15685 드래곤커브
//2019-04-08
public class Main {
    static int[] dy = { 0, -1, 0, 1 };
    static int[] dx = { 1, 0, -1, 0 }; // 오 상 왼 하
    private static boolean[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 드래곤 커브의 개수
        map = new boolean[103][103];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
 
            bfs(x, y, d, g);
        }
 
        
        int ans =0;
        for(int i=0;i<100;i++) {
            for(int j=0;j<100;j++) {
                if(map[i][j]&&map[i+1][j]&&map[i][j+1]&&map[i+1][j+1]) {
                //    System.out.println(i+" "+j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
 
    }
 
    public static void bfs(int x, int y, int d, int generation) {
        Deque<Integer> now = new LinkedList<>();
 
        Deque<Integer> next = new LinkedList<>();
        map[y][x]=true;
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>100 || nx<0 || ny>100) return;
        map[ny][nx]=true;
        y=ny;
        x=nx;
        now.add(getNextdir(d));
        if(generation==0) return;
        int g = 0;
        while (!now.isEmpty()) {
            g++;
            int size = now.size();
 
                for(int i=0;i<size;i++) {
                    int dir = now.pop();
                    ny = y+dy[dir];
                    nx = x+dx[dir];
                    if(ny<0 || ny>100 || nx<0 || ny>100) break;
                    
                    map[ny][nx] = true;
                    
                    int nd = getNextdir(dir);
                    
                    next.push(nd);
                    next.add(dir);
                    y=ny;
                    x=nx;
            }
 
            if(g==generation) return;
            now.clear();
            now = new LinkedList<>(next);
            next.clear();
//            y=ny;
//            x=nx;
        }
 
    }
    public static int getNextdir(int d) {
        if(d==3) return 0;
        else return d+1;
    }
 
    static class pair {
        int y;
        int x;
        int dir;
 
        public pair(int y, int x, int dir) {
            super();
            this.y = y;
            this.x = x;
            this.dir = dir;
        }
    }
}
 

<<C++>>

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
 
int n,generation;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
bool map[101][101] = {false};
deque<int> dq;
 
void dragon_curve(int nx,int ny, int g){
    
    queue<int> q;
    
    if(g == generation) return;
    
    int dq_size = dq.size();
    
    for(int i=0;i<dq_size;i++){
        int a = dq.front();
        dq.pop_front();
        q.push(a);
    }
    
    for(int i=0;i<dq_size;i++){
        int d = q.front();
        q.pop();
        dq.push_back(d);
        
        int nd = (d+1)%4;
        
        nx += dx[nd];
        ny += dy[nd];
        
        if(nx <0 || nx >100 || ny<0 || ny>100) continue;
        
        map[nx][ny]= true;
        dq.push_front(nd);
    }
    
    dragon_curve(nx,ny,g+1);
}
 
void count_box(){
    int cnt = 0;
   
    for(int i=0;i<=99;i++){
        for(int j=1;j<=100;j++){
            if(map[i][j] && map[i][j-1] && map[i+1][j] && map[i+1][j-1])
                cnt++;
        }
    }
    printf("%d\n", cnt);
}
 
int main(){
    scanf("%d",&n);
    
    int x,y,d;
    for(int i=0;i<n;i++){
        scanf("%d %d %d %d",&y,&x,&d,&generation);
        while(!dq.empty()) dq.pop_front();
        
        map[x][y] = true;
        x += dx[d];
        y += dy[d];
        map[x][y] = true;
        dq.push_front(d);
        
        dragon_curve(x,y,0);
    }
    
    count_box();
    
    return 0;
}