드래곤 커브

문제

드래곤 커브의 정보가 주어졌을 때, 4개의 꼭짓점이 모두 드래곤 커브의 일부인 1X1 정사각형의 개수를 출력하기.

추가 정보

0세대는 주어지는 시작점과 방향에 따라서 결정이 된다.
이후에 k세대는 k - 1세대의 끝점을 기준으로 90도 방향 시계방향 회전하여 붙인 정보이다.
자세한 문제는 문제페이지에서 확인하기!

thinking...

처음에는 끝점을 찾는 것과 끝점을 기준으로 시계 방향으로 돌리는 방법에 대해서 고민을 해보았다. 하지만 이에 대해서는 구체적인 방법이 떠오르지 않았다.

그래서 0세대부터 이동방향을 확인해보았고 아래와 같은 규칙을 찾아내었다.
1. 모든 이동은 1씩 가고 다른 방향으로 이동하는 모습이다.
2. 나아가 4세대까지 그려보고 확인해보니 특정방향에 따른 회전 후 방향이 규칙성을 보였다.

up(2) to left(3)
right(0) to up(1)
left(2) to down(3)
down(3) to left(0)

위와 같이 방향의 규칙성을 발견하였고, 이에 따른 방향 숫자도 증가하는 것을 확인하였습니다.

추가적으로 이는 이전 세대를 거꾸로 돌면서 실행하면 된다.

구현 순서

1. 사이즈가 100인 그래프를 생성한다.

2. 드래곤 커브에 대한 정보를 입력 받는다.

3. 드래곤 커브별로 반복문 수행해보기

4. 방향과 세대 정보를 가지고 이동경로를 구해보기

5. 구한 이동경로를 통해서 시작점 위치에서부터 이동시켜보면서 graph정보 갱신하기

6. 모든 드래곤 커브 정보들을 graph에 적용했으면 쭉 돌면서 4가지 꼭짓점이 전부 드래곤 커브가 묻어있는지 확인하여 정답 도출하기

구현 코드

# 드래곤 커브에 의해 만들어진 정사각형의 개수 구하기

# x,y의 최대크기인 100만큼의 그래프 배열 생성 하기
size = 100
graph = [[0] * (size + 1) for _ in range(size + 1)]

# 드래콘 커브의 개수 N 입력 받기
n = int(input())

# 드래곤 커브의 정보 입력받기
curves = []
for _ in range(n):
    # x, y를 시작점으로 하고 방향은 d인 g세대
    curves.append(list(map(int, input().split())))

# 특정 방향에 따른 다음 방향 구해주기
def get_next_direction(g):
    g += 1
    if g > 3:
        return 0
    else:
        return g

# 방향과 세대를 통해 이동 루트 구해주기
def find_route(direction, generation):
    # 0 세대는 시작점 하나만 가지고 있다.
    cur_g = [direction]
    # 세대만큼 반복하면서 경로 추가하기
    for _ in range(1, generation + 1):
        temp_g = []
        # 이전 세대의 경로를 거꾸로 하여서 다음 경로를 찾아주기
        for x in cur_g[::-1]:
            temp_g.append(get_next_direction(x))
        # 현재경로에 다음 경로 추가하면 다음 세대 경로가 된다.
        cur_g.extend(temp_g)
    return cur_g

# 경로에 따라 이동해보면서 graph 정보 갱신하기
def move_by_route(routes, x, y):
    # 시작점 방문 처리
    graph[x][y] = 1
    # 오른쪽 x축, 아래쪽 y축
    # 0 : right, 1 : up, 2 : left, 3 : down
    for route in routes:
        if route == 0:
            x += 1
        elif route == 1:
            y -= 1
        elif route == 2:
            x -= 1
        else: # route == 3
            y += 1
        # 이동한 곳 방문 처리
        graph[x][y] = 1

# 드래곤 커브 정보들 돌면서 수행
for curve in curves:
    # 시작점(x, y), 방향 d, 세대 g
    x, y, d, g = curve
    # 방향과 세대에 따른 이동경로 찾아보기
    routes = find_route(d, g)
    # 시작점부터 경로에 따라서 방문처리 하기
    move_by_route(routes, x, y)

# 현재 위치 기준으로, 1.오른쪽, 2. 아래쪽, 3. 우하 방향 찾아주기
steps = [(1, 0), (0, 1), (1, 1)]

# 0 ~ 100까지의 그래프 4꼭지점 방문처리 되어있는 곳 찾아보기
answer = 0
for x in range(size):
    for y in range(size):
        if graph[x][y] == 1:
            is_answer = True
            for step in steps:
                nx = x + step[0]
                ny = y + step[1]
                # 해당 위치가 만족하지 않으면, False & break
                if graph[nx][ny] == 0:
                    is_answer = False
                    break
            # 여기까지 왔을 때, True라면 만족하는 정사각형
            if is_answer:
                answer += 1

# 정답 출력
print(answer)