[BOJ] 백준 15685 드래곤 커브

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 
3
3 3 0 1
4 2 1 3
4 2 2 1

 Output 

4

시작점과 방향 그리고 몇 세대인지를 이용해 어디까지 좌표를 형성하는지 확인하는 문제.

이전 단계의 모양이 시계방향으로 그려지는 것을 확인할 수 있다.

모양 자체를 통해 해석하면 그림 자체가 시계방향으로 회전해서 이어붙이는 형태이지만

 

시계방향 회전을 코드적으로 구현하기에는 그 규칙이 쉽지 않다.

출발점에서 N세대까지 어떻게 진행했는지 방향을 분석해보자.

    0세대 : →

    1세대 : → / ↑ 

    2세대 : → ↑ / ← ↑

    3세대 : → ↑  ← ↑ / ← ↓ ← ↑

(슬러쉬 '/'는 이전 단계의 끝점에 해당된다.)

 

이전 단계의 화살표 진행 방향들이 리스트에 담겨있다고 가정하고,

다음 단계에서 뒤에서 부터 읽는다고 할 때, 아래의 규칙대로 행해지는 것을 알 수 있다.

    ↑   는 ← 이 되고

    ← 는 ↓   이 되고

    ↓   는 → 이 되고

    → 는 ↑   이 된다.

 

3세대 일 때, 아래와 같이 나타낼 수 있다.

방향은 0~3 이므로 아래와 같이 바꿔 표현할 수 있다.

    1 은 2가 되고

    2 는 3이 되고

    3 은 0이 되고

    0 은 1이 된다.

이를  Dnext = (Dcurrent + 1) % 4 로 일반화할 수 있다.

 

# 첫 번째 입력을 힌트를 통해 연습해보자.

3
3 3 0 1
4 2 1 3
4 2 2 1

0: x좌표가 증가하는 방향 (→) / 1: y좌표가 감소하는 방향 (↑)

2: x좌표가 감소하는 방향 (←) / 3: y좌표가 증가하는 방향 (↓)

결과를 출력할 때 선분으로 둘러쌓여진 정사각형의 개수가 아닌

꼭지점으로 둘러싸져 있는 정사각형의 개수이다.

모든 배열의 꼭지점을 뒤져서 문제에서 만족하는 사각형의 개수인지 체크한다.

 

단계적으로 하면 접근해보면

1. 한 개의 드래곤 커브가 주어질 때 규칙에 맞게 구현

2. N개의 드래곤 커브를 위에서 구현한 것을 이용해 적용

3. 모든 드래곤 커브가 행해진 배열에서 문제에서 요구한 결과값을 탐색하고 출력

---

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.next());
        // 0 <= x,y <= 100
        // 칸이 최대 100칸이므로 좌표 자체는 101개가 되는 셈이다.
        int[][] arr = new int[102][102];
        
        
        
        for(int i=0; i<N; i++) {
            Curve curve = new Curve(Integer.parseInt(sc.next()), Integer.parseInt(sc.next()));
            int d = Integer.parseInt(sc.next());
            int g = Integer.parseInt(sc.next());
            
            // 꼭지점 표시
            arr[curve.x][curve.y] = 1;
            
            // 0 <= g <= 10 이므로 0세대를 우선적으로 한 번 진행
            curve.changePosition(d);
            arr[curve.x][curve.y] = 1;
            
            // 시작 방향을 list에 넣는다.
            List<Integer> list = new LinkedList<>();
            list.add(d);
            
            // 현재 드래곤 커브의 1세대 ~ g세대까지 수행
            for(int j=1; j<=g; j++) {
                
                // 현재 리스트에 쌓여있는 만큼 진행(뒤에서 원소를 탐색)
                int current_size = list.size()-1;
                for(int k=current_size; k>=0 ; k--) {
                    
                    // 이전 단계에서 진행했던 방향들을 하나씩 탐색해서 현재 지점(끝점)에서 그려간다.
                    int next_direction = (list.get(k)+1) % 4;
                    curve.changePosition(next_direction);
                    arr[curve.x][curve.y] = 1;
                    // 진행했던 방향을 리스트에 저장해서 다음 g세대에 사용
                    list.add(next_direction);
                }
            }
            
        }
        
        int answer = 0;
        for(int y=0; y<102; y++) {
            for(int x=0; x<102; x++) {
                if(arr[x][y] == 1) {
                    // 배열의 초과하지 않는 범위 내에서 4 꼭지점이 드래곤 커브되었는지 확인
                    if(x+1 < 102 && y+1 < 102) {
                        if(arr[x+1][y] == 1 && arr[x][y+1] == 1 && arr[x+1][y+1] == 1) {
                            answer++;
                        }
                    }
                }
            }            
        }
        System.out.println(answer);
    }
}

class Curve{
    int x, y;
    
    public Curve(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 문제조건상 격자(배열의 크기)를 벗어나는 경우는 고려하지 않는다.
    public void changePosition(int d) {
        if(d == 0) {
            x++;
        }else if(d == 1) {
            y--;
        }else if(d == 2) {
            x--;
        }else { // d == 3
            y++;
        }
    }
}