[Baekjoon] 15685번 드래곤 커브 (Java) 문제 풀이 [Gold 3]

문제

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

어떻게 풀 것인가?

문제를 처음 읽어보신 분들이라면 아마, 문제가 해괴하다고 느낄지 모른다. 적어도 나는 그랬다. 처음에 문제를 읽었을 때 좌표 개념이 나와서 BFS나 DFS를 생각했다. 하지만 결국엔 문제가 풀리지 않아서, 다른 분의 풀이를 참고하고 나서 단순 구현 및 시뮬레이션 문제라는 점을 발견했다.

 

문제를 읽었을 때 가장 어려운 부분은 아마 "다음 N-1세대 드래곤 커브의 끝 점에 붙인 것" 이 부분일 것이다. 이러한 부분은 결국엔

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

위와 같은 코드로 변환할 수 있다.

 

즉, 우리가 구현문제를 많이 풀었을 때, 저러한 dx,dy와 같은 int 배열을 이용하여 풀었던 경험을 살짝 다른 말로 풀어 쓴 것이다.

 

그렇다면 방향이 처음에 주어졌을 때 다음 방향은 어떤식으로 정해야할까?

나는 1 -> 2 -> 3 -> 4 -> 1 -> 2...... 이러한 점에서 방향을 얻고 아래와 같은 코드를 구성했다.

        List<Integer> d_list = new ArrayList<>();
        d_list.add(d);

        for (int i = 1; i <= g; i++) {
            for (int j = d_list.size() - 1; j >= 0; j--) {
                d_list.add((d_list.get(j) + 1) % 4);
            }
        }

 

풀면서 놓쳤던점

처음에 문제를 읽을 때 좌표라는 개념에서 난항을 겪었다.

 

이 문제를 통해 얻어갈 것

구현, 시뮬레이션 연습

 

내 코드 

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

class Main {
    static boolean[][] map = new boolean[101][101];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int 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());   // 세대

            simulation(x, y, d, g);
        }

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
                    result++;
                }
            }
        }

        System.out.println(result);
    }

    public static void simulation(int x, int y, int d, int g) {
        List<Integer> d_list = new ArrayList<>();
        d_list.add(d);

        for (int i = 1; i <= g; i++) {
            for (int j = d_list.size() - 1; j >= 0; j--) {
                d_list.add((d_list.get(j) + 1) % 4);
            }
        }

        map[y][x] = true;
        for (Integer direction : d_list) {
            x += dx[direction];
            y += dy[direction];
            map[y][x] = true;
        }
    }
}

 

참고

X