이번에 풀어본 문제는
백준 15685번 드래곤 커브 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;

class Curve
{
    int x,y,dir,gen;

    public Curve(int x, int y, int dir, int gen)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.gen = gen;
    }
}
public class Main {
    static boolean [][] map;
    static List<Curve> input;
    static int answer = 0;
    static int [] dx = {0,-1,0,1};
    static int [] dy = {1,0,-1,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new boolean[101][101];
        input = new ArrayList<>();

        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < t; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            int gen = Integer.parseInt(st.nextToken());

            input.add(new Curve(x,y,dir,gen));
        }

        List<Integer> dir_list;
        for(Curve c : input)
        {
            dir_list = new ArrayList<>();
            dir_list.add(c.dir);
            for(int i = 0; i < c.gen; ++i)
            {
                for(int j = dir_list.size()-1; j >= 0; --j)
                {
                    dir_list.add((dir_list.get(j)+1) % 4);
                }
            }
            curve(c,dir_list);
        }
        countSquare();
        System.out.print(answer);
    }
    static void curve(Curve c, List<Integer> list)
    {
        int x = c.x;
        int y = c.y;
        map[x][y] = true;
        for(int dir : list)
        {
            x += dx[dir];
            y += dy[dir];
            map[x][y] = true;
        }
    }
    static void countSquare()
    {
        for(int i = 0; i < 100; ++i)
        {
            for(int j = 0; j < 100; ++j)
            {
                if(map[i][j])
                {
                    if(map[i][j+1] && map[i+1][j+1] && map[i+1][j]) answer++;
                }
            }
        }
    }
}

📝 풀이

주어진 좌표로부터의 드래곤커브를 모두 구하고, 커브내에 포함된 1x1크기의 정사각형 갯수를 찾는 문제입니다.
좌표의 연결 여부만 가지고 있으면 되므로 map 배열은 boolean 자료형을 채택했습니다.
입력된 좌표와 방향을 input리스트에 담고, 하나씩 꺼내며 드래곤 커브를 생성해줍니다.
우선 시작점에 관계없이, 누적된 방향값(dir_list)을 역순으로 탐색해보면 방향이 반시계방향으로 전환된다는 규칙을 찾을 수 있습니다.
따라서 dir_list에 값을 누적시켜주고, 세대가 증가할 때마다 역순으로 탐색하여 방향값을 반시계방향으로 돌린 방향(+1)해줍니다.
입력된 각 좌표를 기준으로 드래곤커브를 모두 생성했다면, 마지막으로 정사각형의 갯수를 카운트하여 answer을 증가시켜줍니다.

📜 후기

본능적으로 커브의 모양에 포커스를 맞춰 풀다보니 규칙을 찾기가 쉽지않은 문제였습니다. 처음부터 진행방향을 기준으로 접근했으면 조금 쉽게 풀었을 것 같은 문제입니다.