15685 - 드래곤 커브

 

---

 

문제

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

15685번: 드래곤 커브

 

풀이

 

문제를 풀기전, 해당 문제의 x와 y값을 잘 참조하자.

 

처음에 이게 헷갈려서 문제 이해를 못하고 있었다.

 

해당 문제 풀이의 핵심은 시계방향으로 회전하고, 그 방향을 계속 저장해주는것이다.

 

우선 격자를 이동할 배열 순서를 → ↑ ← ↓ 순으로 저장한다.

 

0방향으로 시작하는 드래곤 세대들을 살펴보면

 

※ 0세대 : → 

 

※ 1세대 : → ↑

 

※ 2세대 : → ↑ ← ↑

 

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

 

순으로 정리할 수 있다.

 

다음세대는 우선적으로 그 전세대의 값을 가져오고, 추가적인 길이를 갖게된다.

이 때, 그 전 세대에서 뒤의 값부터 가져오면서 이동배열의 다음값을 저장하면 된다.

 

예시로 3세대 같은 경우에 2세대의 값을 모두 가져오고 ( → ↑ ← ↑ ) , 2세대의 뒤의 값부터 하나씩 체크한다. 

가장 뒤의 값은 ↑ 이니까 이동 배열에서 ↑ 다음 값을 저장한다. ( ← 을 저장하면 된다.)

그 다음은 ← 값이고, 이동 배열에서 ← 다음은 ↓ 값이므로 저장해주면 된다.

 

위와 같은 로직으로 드래곤 로드가 시작할 수 있는 4개 방향에 대해서 10세대까지 모두 만들어준후에, 2차원 배열에서 방문한 위치를 체크해주면 된다.

 

이후에 사각형 체크는 왼쪽 상단 꼭짓점을 기준으로 하단, 우, 대각우하단이 모두 방문되었는지 확인하면 된다.

 

 

 

코드

import copy

def bfs(x, y, d, g):
    global visited, dragons, dy, dx

    # y는 열 x는 행
    # 오른쪽으로 가는것 -> [][여기] 값이 변하는것 (0, 2)
    # 위로 가는것 -> [여기][] 값이 변하는것  (1, 3)
    dy = [0, -1, 0, 1]
    dx = [1, 0, -1, 0]

    version = dragons[d][g]
    visited[y][x] = 1
    for v in version:
        y = y + dy[v]
        x = x + dx[v]
        visited[y][x] = 1


def rotate(v):
    if v == 3:
        return 0
    return v+1

def makedragon(before):
    temp = copy.deepcopy(before)
    l = len(before)-1
    for i in range(l, -1, -1):
        temp.append(rotate(before[i]))
    return temp

n = int(input())

dragons = [ [] * 11 for _ in range(4) ]

# 초기값 설정
dragons[0].append([0])
dragons[1].append([1])
dragons[2].append([2])
dragons[3].append([3])
answer = 0
# 4방향, 드래곤 커브를 10세대까지 만들어둔다.
for i in range(4):
    for j in range(1, 11):
        dragons[i].append(makedragon(dragons[i][j-1]))


visited = [[0] * 101 for _ in range(101)]
for _ in range(n):
    x, y, d, g = map(int, input().split())
    bfs(x, y, d, g)


for i in range(100):
    for j in range(100):
        if visited[i][j] == 1 and visited[i+1][j+1] == 1 and visited[i+1][j] == 1 and visited[i][j+1] == 1:
            answer += 1
print(answer)

 

후기

 

평소에 사용하는 x, y가 아니라 반대값이 굉장히 헷갈렸다.덕분에 문제풀이보다 해석에 시간이 더 걸린거 같다.