[BOJ 백준 알고리즘][삼성전자 기출] 15685번 문제/드래곤 커브

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

15685번: 드래곤 커브

문제

그림이 너무 많다. 위 링크에서 보고 오시라.

---

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

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

---

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

---

예제는 생략한다

접근방향

삼성전자 코테 전형의 기출문제라고 한다.

삼성은 확실히 구현, 그래프 탐색에 중점을 두고 문제를 출제하는 거 같다. 

또한 요구사항이 비교적 많고, 이를 실수 없이 구현해야 정답을 얻을 수 있는 거 같다.

 

이 문제 또한 비슷한 문제이다. 드래곤 커브라는 있어 보이는 이름은 됐다치고

무엇보다 문제 설명이 정말 길고 복잡하다.

역시 삼성... 일단 문제를 천천히 살펴보자.

 

일단 드래곤 커브라지만 굳이 선의 정보를 저장할 필요는 없을 거 같다.

90도 단위 회전이고 각 좌표만 독립적으로 회전시켜주면 되니 좌표를 list 같은 거에 저장해주면 될 거 같다.

 

그러고 세대를 진화시키는 건 커브의 마지막 좌표를 회전축 삼아 -90도 회전한 점들을 추가해주면 된다.

이때 마지막 좌표는 추가하지 않는다.

 

그러면 우선 좌표를 회전하는 함수를 구현해주면 될 거 같다.

고등학교 시절 배운 회전변환을 활용하면 쉽게 구현할 수 있다.

 

위키백과를 참조하자. 개인적으로 이런 유형의 문제를 풀 때 알아놓으면 편하다고 생각한다.

 

https://ko.wikipedia.org/wiki/%ED%9A%8C%EC%A0%84%EB%B3%80%ED%99%98%ED%96%89%EB%A0%AC

회전변환행렬 - 위키백과, 우리 모두의 백과사전

 

회전한 점들을 stack에 계속 쌓아나가는 방식으로 커브의 진화 함수를 구현하면 될 거 같다.

이때 나의 경우 좌표가 격자 범위를 벗어나지 않도록 체크해줬지만 문제에서는 범위를 벗어나는 경우는 나오지 않으니 필수는 아닌 거 같다.

 

정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부라는 게 헷갈릴 수도 있겠다.

이건 문제에서 제시한 힌트를 보면 이해가 간다.

예를 들자면 문제의 힌트의 격자를 기준으로 (0, 0), (0, 1), (1, 1), (1, 0) 좌표는 하나의 정사각형을 이룬다.

이 네 좌표가 모두 드래곤 커브에 속해있으면 답의 개수가 하나 증가하는 셈이다.

 

작성 코드

def check(x, y, c, r):
    return (x >= 0 and x < c and y >= 0 and y < r)

def rotate(x, y, ax, ay):
    return y - ay + ax, ax - x + ay

def evolve(curves, board):
    new_curves = []
    rx, ry = curves[-1]
    for curve in curves[:-1]:
        x, y = curve
        rrx, rry = rotate(x, -y, rx, -ry)
        if(check(rrx, -rry, 101, 101)):
            new_curves.append((rrx, -rry))
            board[-rry][rrx] += 1
    return new_curves[::-1], board

def main():
    n = int(input())
    board = [[0 for _ in range(101)] for _ in range(101)]
    dirs = [(1,0),(0,-1),(-1,0),(0,1)]
    for _ in range(n):
        x, y, d, g = map(int, input().split(" "))
        dx,dy=dirs[d]
        curves = [(x, y), (x+dx, y+dy)]
        board[y][x] += 1
        board[y+dy][x+dx] += 1
        for i in range(g):
            ncurves, board = evolve(curves, board)
            curves += ncurves

    answer = 0
    for y in range(100):
        for x in range(100):
            if(board[y][x] and board[y+1][x] and board[y][x+1] and board[y+1][x+1]):
                answer += 1
    print(answer)

if __name__ == "__main__":
    main()