[BOJ] 백준 15685 드래곤 커브 - Python/Java

15685번: 드래곤 커브

 

문제를 한 두 세번정도 읽으면서 이해를 하고, 그대로 구현해주면 되는 문제입니다. 다만, 이 문제에서 X가 증가하는 방향이 오른쪽이고, Y가 증가하는 방향이 아래쪽이라는 점에서 일반적인 이차원 리스트의 인덱싱과 조금 다른데요. 이 부분은 X, Y를 그냥 바꿔서 생각하면 됩니다. 그런데 저는 그냥 있는 그대로 X, Y를 사용했습니다.

 

한편, 이 문제의 핵심은 "이전 세대의 드래곤 커브가 현재 세대의 드래곤 커브를 만드는 데 사용된다"는 점과, "이전 세대의 마지막 점을 기준으로 그 점들이 90도 회전변환된다"는 점입니다.

 

1) 따라서 이전 세대와 현재 세대의 드래곤 커브를 구분하기 위해 prevGen, newGen이라는 리스트를 사용하기로 했고, prevGen으로 newGen을 만들면, prevGen에 newGen의 모든 원소를 더해줬습니다.

 

2) 90도 시계 방향으로 회전된다는 것은 수학적으로는 -90도 회전변환과 같은데요. 또한, 원점이 아닌 점을 기준으로 회전변환이기 때문에 고등학교 때 배운 회전변환의 행렬 공식과 평행 이동 공식을 사용해줬습니다. cos, sin을 이용하면 되죠!

 

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline
n = int(input())
answer = 0
points = [[False] * 101 for _ in range(101)] # 드래곤 커브가 지나가는 좌표들
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1] # 0,1,2,3 방향
for _ in range(n):
    preGen = []
    x, y, direction, generation = map(int, input().split())
    # 0 세대의 드래곤 커브 추가
    preGen = [(x,y), (x + dx[direction], y + dy[direction])]
    points[x][y] = True
    points[x+dx[direction]][y+dy[direction]] = True
    
    while generation > 0:
        generation -= 1
        last_x, last_y = preGen[-1] # 이전 세대의 끝점
        newGen = []
        
        for x, y in preGen[:-1][::-1]:
            # 이전 세대의 드래곤 커브를 끝점을 기준으로 90도 회전
            nx, ny = (y - last_y) * (-1) + last_x, (x - last_x) + last_y
            points[nx][ny] = True
            newGen.append((nx,ny))
        preGen.extend(newGen)
        
for i in range(100):
    for j in range(100):
        if all([points[i][j], points[i][j+1], points[i+1][j], points[i+1][j+1]]):
            answer += 1

print(answer)

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class B_15685 {
    static int n;
    static int answer;
    static boolean[][] check = new boolean[101][101];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++){
            StringTokenizer 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());

            List<Point> prevGen = new ArrayList<>();
            // 0세대의 드래곤 커브가 지나는 점 추가
            prevGen.add(new Point(x, y));
            prevGen.add(new Point(x + dx[d], y + dy[d]));
            check[x][y] = true; check[x+dx[d]][y+dy[d]] = true;
            while (g-- > 0){
                // 이전 세대의 끝점
                int last_x = prevGen.get(prevGen.size() - 1).x;
                int last_y = prevGen.get(prevGen.size() - 1).y;

                // 이전 세대의 마지막 점부터 끝점을 기준으로 90도 회전해서 새로운 세대의 점들 생성
                List<Point> newGen = new ArrayList<>();
                for(int j = prevGen.size() - 1; j >= 0; j--){
                    x = prevGen.get(j).x; y = prevGen.get(j).y;
                    int nx = (y - last_y) * (-1) + last_x;
                    int ny = (x - last_x) + last_y;
                    check[nx][ny] = true;
                    newGen.add(new Point(nx,ny));
                }
                prevGen.addAll(newGen);
            }
        }
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                if(check[i][j] && check[i+1][j] && check[i][j+1] && check[i+1][j+1]) answer++;
            }
        }
        System.out.println(answer);
    }

    static class Point{
        int x, y;
        Point(int x, int y){
            this.x = x; this.y = y;
        }
    }
}