[python 백준] 15685번 드래곤 커브

문제링크

15685번: 드래곤 커브

문제 설명

• 일정한 규칙에 따라 세대를 거듭해 성장하는 드레곤 커브를 구현하면 되는 구현 문제
• 드래곤 커브가 성장하는 규칙을 어떻게 구현할 지 생각해내는 것이 어려운 문제

고민한 부분

드래곤 커브가 성장하는 규칙은 K 세대의 커브의 끝 점을 기준으로 K 세대의 커브 전체를 시계 방향으로 90도 회전시켜 붙인 것이다.

• 이전 세대의 마지막 점부터 시작점까지 역순으로 이동해 온 경로의 역순으로 이동한 방향을 반시계 방향으로 90도 회전시켜 그에 맞게 커브를 성장시키면 된다. 아래 그림을 보면 이해하기 쉽다.
  1. 2세대 커브는 [우 상 좌 상]으로 이동하며 그려짐
  2. 3세대 커브는 2세대 커브가 그려진 순서의 역순 [상 좌 상 우]를 각각 반시계 방향으로 회전시킨 방향인 [좌 하 좌 상] 순서로 선분을 추가해준다.
• 세대가 거듭할 때 이런 식으로 누적된 경로를 역순으로 회전시킨 방향으로 이동하면 드래곤 커브가 완성된다.
• 아래 path_list가 이런 기능을 구현하는 함수로 가장 중요하다.

드래곤 커브 성장 예시

	import sys
	# 방향은 우 상 좌 하 순서
	table = [[0]*101 for i in range$101$]
	def path_list$d,g$:
	path= [d]
	for gen in range$g$:
	for i in range$len(path$-1, -1, -1):
	path.append$(path[i] + 1$%4) ## 돌아가는 순서 잘못됨
	return path
	def count_square:
	global table
	cnt = 0
	for r in range$100$:
	for c in range$100$:
	if (table[r][c] == 1 and
	table[r+1][c] == 1 and
	table[r][c+1] == 1 and
	table[r+1][c+1] == 1):
	cnt += 1
	return cnt
	def plot_curves$curves$:
	global table
	dr = [0,-1,0,1]
	dc = [1,0,-1,0]
	for $c,r,d,g$ in curves:
	path = path_list$d,g$
	table[r][c] = 1
	for i in path:
	r, c = r + dr[i], c + dc[i]
	table[r][c] = 1
	if __name__ == '__main__':
	turn_in = 1
	if turn_in ==0:
	sys.stdio = open$'test_case.txt'$
	N = int$sys.stdio.readline($)
	curves = [list$map(int, sys.stdio.readline($.split)) for i in range$N$]
	else:
	N = int$sys.stdin.readline($)
	curves = [list$map(int, sys.stdin.readline($.split)) for i in range$N$]
	plot_curves$curves$
	print$count_square($)

view raw boj_15685.py hosted with ❤ by GitHub

Lesson learned

• BFS, DFS나 다이나믹 프로그래밍과 같이 특정한 방법을 알고 있어야 푸는 문제가 아닌 단순 구현 문제는 문제를 잘 읽고 그 조건을 구현하면 되기 때문에 틀리고 난 후에 명확하게 배울 수 있는 점을 찾기 어렵다.
• 지금까지 구현 문제를 풀며 반복되는 실수는 문제를 잘못 이해하거나 조건을 누락하며 읽는 실수를 많이 한다는 점이다.
  • 규칙에 따라 방향을 바꾸는 경우 시계 방향, 반시계 방향을 헷갈리는 등의 실수를 자주하는 것을 깨달았다.