문제

BOJ 15685: 드래곤 커브 https://www.acmicpc.net/problem/15685

풀이

조건

• x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다.
• K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
• 방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.
  • 0: x좌표가 증가하는 방향 (→)
    1: y좌표가 감소하는 방향 (↑)
    2: x좌표가 감소하는 방향 (←)
    3: y좌표가 증가하는 방향 (↓)

풀이 순서

• List에 처음 입력받은 방향값을 넣는다.
• 입력 받은 세대(g) 만큼 반복하며 List에 새로 구한 방향값을 넣는다.
  • 새로 구한 방향값 : List의 마지막 값을 꺼낸 다음 시계 방향 90도로 회전 시킨 값
    • (List의 마지막 값 + 1) % 4
• 입력 받은 세대(g) 만큼 반복이 끝나면 List에 들어있는 방향값을 모두 꺼내며 선분의 양 끝의 좌표를 구한다.(이 때 정수 1을 넣어 표시한다)
• 변의 길이가 1인 정사각형의 각 꼭짓점을 탐색하며 구한다.(각 꼭짓점은 1로 되어있음)

코드

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

public class Main {
    
	static int N;
	static int x, y, d, g;
	static int[][] map;
	
	static int[] dx = {1, 0, -1, 0}; // d가 0, 1, 2, 3 일 때 순서대로 방향 나타냄
	static int[] dy = {0, -1, 0, 1};
	
	static int ans = 0;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	
    	N = Integer.parseInt(br.readLine());
    	map = new int[101][101];
    	
    	for(int i=1; i<=N; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		
    		x = Integer.parseInt(st.nextToken());
    		y = Integer.parseInt(st.nextToken());
    		d = Integer.parseInt(st.nextToken());
    		g = Integer.parseInt(st.nextToken());
    		
    		dragonCurve(x, y, d, g);
    	}
    	
    	// 변의 길이가 1인 정사각형의 각 꼭짓점을 확인하는 과정(각 꼭짓점은 1로 되어있음)
    	for(int i=0; i<100; i++) {
    		for(int j=0; j<100; j++) {
    			if(map[i][j] == 1 && map[i][j+1] == 1 && map[i+1][j] == 1 && map[i+1][j+1] == 1) {
    				ans++;
    			}
    		}
    	}
    	
    	System.out.println(ans);
    }
    
    static void dragonCurve(int x, int y, int d, int g) {
    	// 리스트에 방향값을 넣음
    	List<Integer> dList = new ArrayList<>();
    	dList.add(d); // 최초 값 넣음
    	
    	// 입력 받은 세대(g)만큼 반복하며 방향 넣음
    	for(int i=1; i<=g; i++) {
    		// 리스트의 마지막 값을 통해 90도 시계방향으로 회전한 방향 값을 리스트에 넣어줌
    		for(int j=dList.size() - 1; j>=0; j--) {
    			dList.add((dList.get(j) + 1) % 4);
    		}
    	}
    	
    	// 리스트에 있는 방향값을 통해 선분의 양 끝을 1로 갱신해줌
    	map[y][x] = 1; 
    	for(Integer t : dList) {
    		x += dx[t];
    		y += dy[t];
    		map[y][x] = 1;
    	}
    }
    
}

정리

• 반복되는 모양이 있어 재귀를 사용해야 하나 고민했는데 아니었다.
• 문제의 흐름처럼 이전 모양을 회전시키면 너무 복잡해져서 방향 값이 바뀐다는 규칙을 찾아 해결했다.