15685: 드래곤 커브

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

15685번: 드래곤 커브

설명

우선, 크기가 100 x 100 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1 x 1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램 작성. ( 0 <= x,y <= 100 ). 드래곤 커브는 총 3가지 속성이 있으며 x축은의 방향은 행, y축 방향은 열이다.

1. 시작 점
2. 시작 방향
3. 세대

초기 0세대 드래곤 커브는 길이가 1인 선분이다. 다음 그림처럼 (0,0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 초기: 시작점-(0,0), 시작 방향-오른쪽, 세대-0

이후 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙이는 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미.

2세대 드래곤 커브도 1세대 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해서 만들 수 있다. 90도 시계 방향 회전한 것을 이전 커브 끝점에 붙인다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

핵심 아이디어

• 구현, 시뮬레이션 문제
• 방향을 문제를 보고 잘 설정하자
• 이전 커브를 90도 시계 방향으로 회전 시킨 다음 끝점에 붙인다.

세대가 반복할 수록 추가되는 방향에는 규칙이 존재한다. 이전 세대의 방향을 뒤집은 값에 +1 한 값이 다음 세대의 방향이다. 

즉 규칙은 다음과 같다. 이전 세대의 정보를 뒤집어 거기에 1을 더해주면 된다. 그리고 4면 다시 처음인 0으로 돌려주면 된다.

• 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 ...

이런식으로 규칙을 찾을 수 있다. 따라서 세대가 늘어날 때마다 찾았던 규칙을 이용해서 방향을 계산해주고, 그에 지나간 좌표를 표시해주면 된다. 그래서 중요한 점은 한 세대의 방향을 하나로 보는 것이 아닌 쪼개서 생각하고, 규칙을 찾아야한다. 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

코드 구현

# 1.

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

 

# 2.

for _ in range(n):
	x,y,d,g = map(int, input().split())
	dragon = [d]
	check[x][y] = 1
	for i in range(g):
		for j in range(len(dragon)-1,-1,-1):
			dragon.append((dragon[j] + 1) % 4)

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

# 방향 정의  0 1 2 3, x,y 좌표가 바뀜
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

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

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

ans = 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:
			ans += 1
print(ans)