15685번 - 드래곤 커브

문제

 

15685번: 드래곤 커브 (acmicpc.net)

15685번: 드래곤 커브

풀이 1

역시나 문제를 제대로 읽지 않고 풀어 굉장히 많은 시간을 허비했다. 제한조건에 보면 0 ≤ x, y ≤ 100 으로 주어지는데, 내 마음대로 0 ≤ x, y < 100 로 풀면서 "맞왜틀?" 하고 있었다. 이것 외에도 끝점을 기준으로 90도 돌린다는 의미를 방향벡터를 그저 시계방향으로 90도 꺾는다는 것으로 접근해서 틀리기도 했다.

아무튼 끝점에서 이전의 점들의 방향벡터를 90도 꺾어서 그리기만 하면 된다는것만 파악하면 매우 쉬운 문제고, 재귀함수로 풀 수도 있지만 반복문으로 충분히 풀이 가능한 문제이다.

from collections import deque

# 동 북 서 남
direction = [(0,1), (-1,0), (0,-1), (1,0)]

N = int(input())
board = [[0]*101 for _ in range(101)]
for _ in range(N):
    x,y,d,g = map(int, input().split())
    board[y][x] = 1
    cnt = 0
    coor = [(y,x)]
    vectors = [direction[d]]
    while cnt <= g:
        row, col = coor[-1]
        for vector in vectors:
            nRow, nCol = row + vector[0], col + vector[1]
            coor.append((nRow, nCol))
            board[nRow][nCol] = 1
        vectors = deque()
        for i in range(2 ** cnt):
            new_vector = (coor[i][0] - coor[-1][0], coor[i][1] - coor[-1][1])
            vectors.appendleft((new_vector[1], -new_vector[0]))
        cnt += 1

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

 

풀이 2

끝점을 기준으로 시계방향으로 90도 돌렸을 때의 방향은 원점을 기준으로 반시계 방향으로 90도 돌렸을 때와 같다. 위 풀이 처럼 벡터를 두고 풀이해도 되지만, 좀 더 간단하게 단순히 방향에 1씩만 더해줘도 된다.

N = int(input())
board = [[0]*101 for _ in range(101)]

# 동 북 서 남
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


for _ in range(N):
    x,y,d,g = map(int,input().split())
    # 드래곤 커브 방향
    dirs = []
    dirs.append(d)
    for i in range(g):
        new_dirs = [*dirs]
        for dir in dirs[::-1]:
            new_dirs.append((dir+1)%4)
        dirs = new_dirs
    # 드래곤 커브 그리기
    board[y][x] = 1
    for dir in dirs:
        y += dy[dir]
        x += dx[dir]
        board[y][x] = 1

answer = 0
for row in range(0,100):
    for col in range(0,100):
        if all(board[row][col:col+2]) and all(board[row+1][col:col+2]):
            answer += 1
print(answer)