[백준] 15685번 드래곤 커브 (Python)

백준 15685 드래곤 커브

문제에서 설명을 보면서 좌표를 조금 더 신경 쓰고 보면 이해하기 편했던 문제다. 단순 구현이지만, 좋은 솔루션을 보고 내 코드를 개선했다. DP를 활용해서 시간 복잡도를 줄일 수 있었다. dp 리스트를 좌표가 아닌 방향으로 저장하는 것이 코드를 줄이는 방법이었다. 또한, 방향으로 dp 리스트를 저장한 만큼 방향의 순서를 지키는 것 또한 중요했다.

1. 진행하는 방향을 저장하여 드래곤 세대별로 dp에 저장한다.
2. 시작하는 방향에 따라 dp에 저장된 방향 또한 for 문을 활용해 변환.
3. 이동 후에, 해당 위치를 업데이트 한 후에, grid 업데이트

import sys

def make_dp(idx):
    while idx + 1 != len(dp):
        dp.append(dp[-1] + [(direction + 1) % 4 for direction in dp[-1][-1::-1]])

def make_dragon(targetY, targetX, d, idx):
    if len(dp) <= idx:
        make_dp(idx)
    grid[targetY][targetX] = 1
    for direction in dp[idx]:
        direction = (direction + d) % 4
        targetY += dy[direction]
        targetX += dx[direction]
        grid[targetY][targetX] = 1

inp = sys.stdin.readline
n = int(inp().strip())
dp = [[0]]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
grid = [[False for _ in range(101)] for _ in range(101)]
for _ in range(n):
    x, y, d, g = map(int, inp().split())
    make_dragon(y, x, d , g)

res = 0
for i in range(100):
    for j in range(100):
        if grid[i][j] and grid[i + 1][j] and grid[i][j + 1] and grid[i + 1][j + 1]:
            res += 1
print(res)

dp에 좌표를 저장한 풀이

import sys

def turn(targetY, targetX, y, x, d):
    y = y - targetY
    x = x - targetX
    for _ in range(d):
        ty = -x
        tx = y
        y, x = ty, tx
    return [targetY + y, targetX + x]

def make_dp(idx):
    while idx + 1 != len(dp):
        tmp = []
        targetY , targetX = dp[-1][-1]
        for y, x in dp[-1][-2::-1]:
            tmp.append(turn(targetY, targetX, y, x, 3))
        dp.append(dp[-1] + tmp)

def make_dragon(targetY, targetX, d, idx):
    if len(dp) <= idx:
        make_dp(idx)
    for y, x in dp[idx]:
        y, x = turn(0, 0, y, x, d)
        grid[targetY + y][targetX + x] = 1

inp = sys.stdin.readline
n = int(inp().strip())
dp = [[[0, 0,], [0, 1]]]
grid = [[0 for _ in range(200)] for _ in range(200)]
for _ in range(n):
    x, y, d, g = map(int, inp().split())
    make_dragon(y, x, d , g)

res = 0
for i in range(200):
    for j in range(200):
        if grid[i][j] == 1 and grid[i + 1][j] == 1 and grid[i][j + 1] == 1 and grid[i + 1][j + 1] == 1:
            res += 1
print(res)