문제 탐색하기

입력 자료 정리

1. n은 드래곤 커브의 개수로 사실상 테스트케이스다
2. 이어서 들어오는 각 값은 (y,x)를 뒤집은 x,y인데 편하게 하기 위해 그냥 x,y로 생각한다
3. d는 방향이다. 0은 우, 1은 상, 2는 좌, 3은 하 방향이다
4. g는 세대다.

해결방법 추론

1. 입력값도 크기도 작고 드래곤 커브를 모두 진행한다음 그냥 정사각형 구하는
   구현문제다
2. 문제 이해만 하면 쉽게 구할 수 있다. 먼저 드래곤 커브의 진행 예시를 확인해보자
3. 다음 세대로 나아갈 수록 바로 직전 세대의 역순으로 (이전 방향 + 1)방향이 생성된다
4. 이점을 이용한다면 미리 모든 세대의 방향을 구해둔 뒤, 하나씩 꺼내서 드래곤 커브를 진행시키면 될 것이다
5. 드래곤 커브는 겹칠 수 있기 때문에 따로 구분할 필요는 없다
6. 완성한 뒤 정사각형을 찾아야하는데, 0,0부터 자신과 자신의 우, 하, 우하 방향의 좌표값을 확인해서 모두 드래곤커브가 지나간 자리면 정답의 개수로 포함시키면 될 것이다

시간복잡도 계산

1. 시간복잡도는 n x g로 생각하려고 했는데, 둘의 최대 연산이 20 x 10이다
2. 반면 모든 좌표를 확인해서 드래곤 커브 정사각형을 구하는 경우는 100 x 100의 연산이 나온다
3. 격자의 세로, 가로 길이를 n으로 정의하면 시간복잡도는 O(n^2)이 되며, 시간제한안에 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n과 x,y,d,g 모두 int형 변수로 관리한다
2. 미리 세대별 방향을 담아둘 리스트를 선언한다. 이 리스트는 드래곤커브마다 독립되어야하므로 n번의 순회 각각에서 초기화한다
3. 격자는 boolean타입의 2차원 배열로 한다. 그 지점을 지났는지만 판단하면 되기 떄문이다
   이때 최대 크기인 101 x 101로 선언해서 0~100인 지점에 모두 표시하도록 한다

구현 코드 설계

1. 0세대 방향은 리스트에 넣고, 최소 지점도 방문체크해둔다

세대별 방향

1. 0세대는 미리 넣었으니 1세대부터 g세대까지 방향을 넣어준다
2. 해당 세대의 방향은 리스트에 담긴 방향을 역순으로 꺼낸 뒤 +1한 방향으로 넣어준다
   이때 0~3범위를 벗어날 수 있으므로 4로 모듈러 연산을 한다

드래곤 커브 진행

1. 이제 방향에 따라 현재 좌표를 바꾸기 위해 ny, nx를 선언한다.
   이 값은 처음 위치의 좌표다
2. 리스트에서 값을 하나씩 꺼내 그 방향으로 이동한 뒤 해당 좌표를 true로 바꾼다

정사각형 탐색

1. 모든 정사각형 좌표를 탐색하며, 현재 좌표, 현재 좌표의 우, 하, 우하 방향이 모두 true인 경우 ans를 증가시킨다

출력값 설계

1. 완성한 ans를 출력하면 정답이 된다.

정답 코드

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

public class Main {

    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        int ans = 0;
        boolean[][] visited = new boolean[101][101];
        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<Integer> list = new ArrayList<>();
            list.add(d);
            for(int j=1; j<g+1; j++){
                for(int k=list.size()-1; k>=0; k--){
                    list.add((list.get(k)+1)%4);
                }
            }

            visited[x][y] = true;
            int nx = x;
            int ny = y;
            for (int j = 0; j < list.size(); j++) {
                int dir = list.get(j);
                nx += dx[dir];
                ny += dy[dir];
                visited[nx][ny] = true;
            }
        }


        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if(visited[i][j] && visited[i+1][j]
                        && visited[i][j+1] && visited[i+1][j+1]){
                    ans++;
                }
            }
        }
        bw.write(ans+"");

        br.close();
        bw.close();
    }
}

문제 링크

15685번 - 드래곤 커브