[백준] 15685(파이썬) - 드래곤 커브

 

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

15685번: 드래곤 커브

• 이 문제는 뭔가 엄청 어려운 거 같았는데 엄청 어려웠던... 문제입니다.
• 하지만 그림을 그려보면서 문제를 읽다보니까 '규칙을 무조건 찾아야겠다'라는 생각이 들었습니다.
• 0,1,2,3의 방향을 가지고 규칙을 찾다보니 방향이 앞에  이전 세대의 정보를 뒤집어 거기에 1을 더해주면 됩니다. 4면 다시 처음인 0으로 돌려주면 됩니다. 이 구현은 4로 나눈 나머지로 계산해주면 됩니다.
  • 0세대 : 0
  • 1세대 : 0 1 (0 , (0+1))
  • 2세대 : 0 1 2 1 (0, 1, (1+1), (0+1))
  • 3세대 : 0 1 2 1 2 3 2 1 (0,1,2,1,(1+1),(2+1),(1+1),(0+1))
  • 4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1 ...
    이런식으로 규칙을 찾을 수 있습니다.
• 세대가 늘어날 때마다 찾았던 규칙을 이용해서 방향을 계산해주고, 그에 따라 지나간 좌표를 표시해주면 됩니다.
• 마지막으로는 좌표가 최대 100,100 이니까 2중 for문을 돌면서 정사각형 하나의 좌표를 모두 지나쳤으면(check가 되어있다면) result에 1을 더해줍니다.
  
• 이 문제에서 제일 중요한 점은 한 세대의 방향을 하나로 보는것이 아닌 쪼개서 생각을 하고, 규칙을 찾는 것이라고 할 수 있죠.
• 자세한 내용은 주석을 참고해주시면 감사하겠습니다.

import sys
input = sys.stdin.readline

n = int(input())

dx = [1,0,-1,0]
dy = [0,-1,0,1]

# 좌표가 드래곤 커브에 포함이 되는지 체크해줄 리스트
check = [[0] * (101) for _ in range(101)]


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

    # 주어진 g세대동안 움직인 방향들을 담아둘 리스트
    move_list = [d]
    # 먼저 시작하는 x,y 좌표는 방문체크
    check[x][y] = 1
    # 세대 만큼 For문을 돌리면서
    for i in range(g):
        tmp = []
        # 시작세대 d로 초기화한 move_list의 길이만 큼 for문을 돌린다.
        # 앞으로 계속 추가해줄 것이기 때문에 길이는 늘어난다.
        for j in range(len(move_list)):
            # 이전 세대들을 돌면서 뒤에서 부터  방향에 1씩 더하고 4로 나눠서 방향을 
            # tmp에 append 시킨다.
            tmp.append((move_list[-j-1]+1)%4)
        # move_list 에 tmp를 extend 시켜서 뒤에 그대로 붙여준다.
        move_list.extend(tmp)


    # g 세대 만큼 실행한 뒤 
    # move_list에 있는 방향들을 확인하면서 좌표를 계산해주고, check 처리를 해준다.
    for i in move_list:
        nx = x + dx[i]
        ny = y + dy[i]
        check[nx][ny] = 1 # 체크처리
        x,y = nx,ny # 방향을 현재 움직인 방향으로 갱신

answer = 0
# 100,100 좌표를 돌면서 한 좌표가 1로 체크되어있을 때, 
# 나머지 오른쪽, 아래, 오른쪽 아래대각선이 1로 체크되어있으면
# answer += 1  을 해준다.
for i in range(100):
    for j in range(100):
        if check[i][j] == 1 and check[i+1][j] == 1 and check[i][j+1] == 1 and check[i+1][j+1] == 1:
            answer += 1

print(answer)