[백준] 15685번 / Java / 드래곤 커브 - 구현, 시뮬레이션

문제 - (https://www.acmicpc.net/problem/15685)

3시간이나 걸렸다ㅠ

다른 사람들은 "방향"에 초점을 맞춰서 "배열"로 문제를 풀어나갔지만 나는 "좌표"로 풀었다..

결과는... 시간도 너무 오래걸렸고 문제 자체도 배열로 풀어나가길 바란듯 하다.

왜냐면, 이 조건 때문이다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

조건에 따르면 y좌표가 감소하는 방향이 ↑인데, 좌표평면은 위로 갈수록 y값이 커진다.

하지만 배열을 이용해서 풀면, 배열은 위로 갈수록 y값(인덱스)이 작아진다.

이런 이유로 문제 출제자도 배열로 풀길 바란 것 같다.

출제의도 완벽히 무시하고 더 어려운 길을 택한 나도 대단한듯

 

방향을 이용한 풀이법은 나중에 다시 풀어볼 때 사용해보도록 하고,3시간이나 공들여서 푼 문제니까... 좌표로 어떻게 풀었는지 적어는 두어야겠다.

 

우선,  큰 틀을 말해보자면

1. list에 좌표들을 추가해나간다.
2. list의 마지막 원소는 다음 드래곤 커브의 기준점이 된다.
3. list의 뒤부터 순회하면서 드래곤 커브를 진행한다. 이 때, 방문하게되는 좌표들을 list에 추가한다.
   • 문제의 규칙을 파악해보면 기준점과 이전에 찍었던 좌표들의 거리차이의 규칙만큼 새로운 드래곤 커브 좌표가 추가되는 것을 알 수 있다.
   • 거리차이의 규칙은 이렇다.
     기준점 x, y와 이전에 찍었던 좌표 p1, p2가 있다고 하면, p1-x, p2-y만큼의 거리차이가 있음을 알 수 있다.
     새롭게 추가되는 좌표는 p1, p2에서 시계방향으로 90도 회전한 위치이므로 기준점과의 거리차이를 반전시킨 값을 더해주어야 한다.
     x-(p1-x), y+(p2-y)가 새롭게 찍히는 드래곤 커브 좌표가 됨을 알 수 있다.
     이 때, x에 p1-x를 빼주는 이유는 x, y와 p1, p2의 거리 차이에서 y좌표가 감소하는 것이 위를 향하는 것이기 때문이다.
4. 전부 추가됐으면 list에 담겨있는 모든 좌표를 순회하여 사각형이 만들어지는 것의 수를 구한다.

문제에서 "드래곤 커브는 서로 겹칠 수 있다"라고 했으므로 중복되는 경우를 없애주기 위해

HashSet을 이용해서 중복을 제거했다.

2020/06/25 - [IT 공부/코딩 스킬] - HashSet - 커스텀 클래스 중복 제거

---

📌주의할 점

• 더 쉽게 풀 수 있는 방법을 생각해본다.
• 문제에서 주어지는 것들은 사용하라고 주는 것들이다. 내 풀이에 문제에서 주어지는 것이 크게 사용되지 않는다면 한 번 의심해볼 필요가 있다. (더 쉬운 방법이 있을 수 있으니 고민해보라는 의미)
• 내가 만든 객체가 있을 때, hashCode를 오버라이딩하여 같은 객체인지 판별할 수 있게 할 수 있다. 더불어 equals까지 오버라이딩하면 동일한 객체인지 판별할 수 있게 할 수 있다. 이 방법으로 HashSet의 중복제거를 구현할 수 있었다.

---

😅실수

• 나는 배열을 사용하지 않고 좌표를 사용했으므로 윗방향으로 향할 때, y값이 증가하는 것이 아니라 감소하는 것을 유념하지 못했다.
• 리스트를 순회할 때, 뒤에서부터 순회해야하는 것을 눈치채지 못해서 시간을 많이 잡아먹었다 ㅠㅠ

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Objects;
import java.util.StringTokenizer;

/**
 * 골드4 - 3시간
 * 밑에 힌트있는데 안봤음.. 하..ㅡㅡ
 * 근데 애초에 너무 어렵게 푼듯.........ㅠㅠ
 */
public class DragonCurve {
    static int n;
    static int[][] dragonInfo;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static ArrayList<Dot> list;
    static int currentG;

    static class Dot {
        int x;
        int y;

        Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (this.getClass() != obj.getClass()) return false;
            return (((Dot) obj).x == this.x) && (((Dot) obj).y == this.y);
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    // 기준점 x,y를 이용하여 드래곤커브를 시뮬레이션 한다.
    static void simulate(Dot sd, int g) {
        // 기저
        if (g == currentG) return;

        int size = list.size() - 2; // 마지막 값은 기준점이므로 제외
        for (int i = size; i >= 0; i--) {
            Dot d = list.get(i);

            int diffX = d.x - sd.x;
            int diffY = d.y - sd.y;

            list.add(new Dot(sd.x -/*실수*/ diffY, sd.y + diffX));
        }
        simulate(list.get(list.size() - 1), g + 1);
    }

    static boolean isSquare(Dot dot, HashSet<Dot> dots){
        int[][] square = {{0,-1},{1,-1},{1,0}};
        for (int i=0;i<square.length;i++){
            int x = dot.x+square[i][0];
            int y = dot.y+square[i][1];
            if (!dots.contains(new Dot(x,y))) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dragonInfo = new int[n][4];
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                dragonInfo[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        HashSet<Dot> res = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // 0세대 드래곤 커브의 좌표를 set에 넣음
            list = new ArrayList<>();

            int x0 = dragonInfo[i][0];
            int y0 = dragonInfo[i][1];
            int d = dragonInfo[i][2];
            currentG = dragonInfo[i][3];

            int x1 = x0 + dx[d];
            int y1 = y0 + dy[d];

            list.add(new Dot(x0, y0));
            list.add(new Dot(x1, y1));

            simulate(list.get(list.size() - 1), 0);

            HashSet<Dot> set = new HashSet<>(list);
            res.addAll(set);
        }

        // result를 가지고 사각형 만들어지는지 확인
        int answer = 0;
        for (Dot d : res) {
            if(isSquare(d, res)) answer++;
        }
        System.out.println(answer);
    }
}