[BOJ] 15685. 드래곤 커브

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

15685번: 드래곤 커브

 

 

1. 해결방법

시뮬레이션 문제이다. 하지만 이동 방향에 대한 규칙을 찾아야하는 무시무시한 방법이 숨어있다.
본인은 가까스로 찾긴했는데 찾아도 다른 부분의 로직을 코드로 옮기는데 한계가 있어 풀이를 참조하였다. 
시간은 2시간정도 걸렸다.

가장 중요한건 드래곤 커브의 방향의 규칙성을 찾는게 중요하다.
0세대 : 0
1세대 : 0 1
2세대 : 0 1 2 1
3세대 : 0 1 2 1 2 3 2 1
4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

이와 같이 4세대까지는 직접 규칙성을 찾는걸 권장한다. 
2세대가 0 1 2 1일때, 3세대에서는 2세대의 방향을 뒤집어서 각 숫자에  +1을 해야하는 규칙이다.

위의 규칙성을 코드로 나타내면 (direct[-i - 1] + 1) % 4가 된다. %4를 하는 이유는 방향에서 4가 없고, 규칙상 4가 들어가야할 자리에는 0으로 갱신된 값이 들어가는 것을 찾을 수 있다.

규칙에 맞게 direct 방향 리스트에 드래곤 커브 방향을 append하고, dy, dx 방향은 문제에서 드래곤 커브가 오른쪽 방향부터 시작한다느 것을 확인 가능하기에 오른쪽부터, 1세대는 위로 향하기에 이에 맞는 방향으로 설정하였다.

direct 리스트를 for문 돌려서 maps에 해당 인덱스 값을 1로 갱신시켜주면 된다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline

# input
N = int(input())
dragons = []
for i in range(N):
    dragons.append(list(map(int, input().split())))

# main
maps = [[0] * 101 for _ in range(101)]
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

for x, y, d, g in dragons:
    maps[y][x] = 1

    direct = [d]
    for num in range(g):
        temp = []
        for i in range(len(direct)):
            temp.append((direct[-i - 1] + 1) % 4)
        direct += temp

    for i in direct:
        ny, nx = y + dy[i], x + dx[i]
        maps[ny][nx] = 1
        y, x = ny, nx

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

print(answer)