BOJ 15685번: 드래곤 커브

문제

문제 바로가기> BOJ 15685번: 드래곤 커브

15685번: 드래곤 커브

 

풀이

드래곤 커브를 살펴보면, 규칙이 있는데,

다음 세대에 추가되는 선분의 방향 = `(이전 세대의 방향 정보를 역순 탐색 + 1) % 4` 를 한 것이 된다.

따라서 해당 규칙에 맞추어서 구현해주었다! 

주의할 점은 역순으로 꺼내서 이어 붙어줘야 하는 것인데, 이 부분은 예제를 살펴보면 쉽게 이해할 수 있을 것 같다.

 

C++

#include<iostream>
#include<vector>
#define MAX 101
using namespace std;

int N;
bool map[MAX][MAX];
int dy[] = {0, -1, 0, 1}; // → ↑ ← ↓
int dx[] = {1, 0, -1, 0};

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

    vector<int> dir;

    // 0 세대 드래콘 커브
    map[y][x] = true;
    y+=dy[d]; x+=dx[d];
    map[y][x] = true;
    dir.push_back(d);

    while(g--){ // g세대 드래곤 커브를 만듦
        for(int i=(int)dir.size()-1; i>=0; i--){ // 거꾸로
            int nd = (dir[i]+1)%4;
            y+=dy[nd]; x+=dx[nd];
            map[y][x] = true;
            dir.push_back(nd);
        }
    }
}

void output(){ // 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력
    int ans = 0;
    for(int i=0; i<MAX-1; i++){
        for(int j=0; j<MAX-1; j++){
            if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]) ans++;
        }
    } cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    int  x, y, d, g; // 드래곤 커브의 시작 점, 방향, 세대
    while(N--){
        cin >> x >> y >> d >> g;
        solution(x, y, d, g); // 드래곤 커브를 만듦
    } output();
}

 

Java

import java.io.*;
import java.util.*;

public class Main {
	
	private static boolean[][] map = new boolean[101][101];
	private static int dy[] = {0, -1, 0, 1};
	private static int dx[] = {1, 0, -1, 0};
	private static int N;

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		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());
			solution(x, y, d, g);
		}
		output();
	}
	
	public static void solution(int x, int y, int d, int g) {
	    List<Integer> dir = new ArrayList<>();

	    // 0 세대 드래콘 커브
	    map[y][x] = true;
	    y+=dy[d]; x+=dx[d];
	    map[y][x] = true;
	    dir.add(d);

	    while(g-- > 0){ // g세대 드래곤 커브를 만듦
	        for(int i=dir.size()-1; i>=0; i--){ // 거꾸로
	            int nd = (dir.get(i)+1)%4;
	            y+=dy[nd]; x+=dx[nd];
	            map[y][x] = true;
	            dir.add(nd);
	        }
	    }
	}
	
	public static void output() {
	    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]) ans++;
	        }
	    } System.out.println(ans);
	}
}