boj 15685 드래곤 커브 (삼성기출)

문제

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

처음에 문제읽고 어떻게 접근해야 하나 막막했던 문제이다
규칙만 찾아내고나면 그 후는 단순 구현이라 어렵지는 않다

드래곤 커브를 직접 그려보면서 문제에 주어진 direction 대로 0,1,2,3 숫자로 적다보면 규칙찾기가 수월하다
처음에 그냥 x,y 좌표 기준으로 변화하는걸 적다보니깐 규칙이 잘 안보여서 어려웠다

이전 세대의 커브 + 이전세대를 reverse하고 각 원소에 +1 해준것이 추가로 붙는 형태이다.
내가 생각한 전체적인 방식은 최종적으로 그려질 드래곤커브를 다 dir대로 리스트로 만들어서
쭉 리스트를 탐색하며 해당 리스트대로 이동한곳의 좌표를 True로 만들어주고

모든 인풋에 대해 처리가 끝나면 최종적으로 네 꼭지점이 모두 True,True,True,True 인 4각형 개수를 체크하는것이다.

사각형 체크하는부분도 완전탐색으로 하지말고 좀더 최적화를 시킬 수 있을것 같긴 한데, 어차피 주어진 크기가 101 * 101이라서 얼마 안걸릴것이라 그냥 다 돌렸다.

아 크기가 100 100 이 아닌 101 101인것에 주의하자

이거때문에 처음 제출했을때 인덱스 에러 났따.

내 풀이

back = [[False] * 101 for _ in range(101)]

back[0][0] = True


def answerCount():
    count = 0
    for i in range(100):
        for j in range(100):
            if back[i][j] == True and back[i+1][j] == True and back[i][j+1] == True and back[i+1][j+1] ==True:
                count += 1

    return count


def makeDragon(d,g):
    result = []
    result.append(d)
    for i in range(g):
        temp = result[::-1]
        result += [(k+1)%4 for k in temp]

    return result

def nextPoint(current,dir):
    if dir == 0:
        np = (current[0]+1,current[1])

    elif dir == 1:
        np = (current[0],current[1]-1)

    elif dir == 2:
        np = (current[0]-1,current[1])

    else :
        np = (current[0],current[1]+1)

    return np


def mapCheck(x,y,d,g):
    doList = makeDragon(d,g)
    current = (x,y)
    back[x][y] = True
    for dir in doList:
        current = nextPoint(current,dir)
        back[current[0]][current[1]] = True


n = int(input())
for _ in range(n):
    x,y,d,g = map(int,input().split())
    mapCheck(x,y,d,g)

print(answerCount())

결과