import sys
input = sys.stdin.readline
def roll(A,B):
if A[0] >= B[0] and A[1] < B[1]:
dx = A[0]-B[0]
dy = B[1]-A[1]
return (B[0]+dy,B[1]+dx)
elif A[0] >= B[0] and A[1] >= B[1]:
dx = A[0] - B[0]
dy = A[1] - B[1]
return (B[0]-dy,B[1]+dx)
elif A[0] < B[0] and A[1] < B[1]:
dx = B[0]-A[0]
dy = B[1]-A[1]
return (B[0]+dy,B[1]-dx)
else:
dx = B[0]-A[0]
dy = A[1]-B[1]
return (B[0]-dy,B[1]-dx)
def dragon(cur_gener,total_gener):
global dragon_list
if cur_gener == total_gener:
return
tail_position = dragon_list[-1]
dragon_length = len(dragon_list)
for ind in range(dragon_length-2,-1,-1):
dragon_list.append(roll(dragon_list[ind],tail_position))
dragon(cur_gener+1,total_gener)
N = int(input())
# x,y 시작점 d는 시작 방향 g는 세대
dx = [1,0,-1,0]
dy = [0,-1,0,1]
arr = [[0]*101 for i in range(101)]
for _ in range(N):
x,y,dire,gener = map(int,input().split())
dragon_list = [(x,y),(x+dx[dire],y+dy[dire])]
if gener:
dragon(0,gener)
for position in dragon_list:
arr[position[1]][position[0]] = 1
result = 0
for y in range(100):
for x in range(100):
if arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x][y+1] == 4:
result += 1
print(result)이 드래곤 커브는 끝에 있는 점을 기준으로 현재까지 온 경로들을 전부 시계 방향으로 90도 회전을 해주는 것을 계속 반복한다.
처음 풀었던 방식은 어렵게 생각해서 푼 문제이다.
드래곤 커브의 각 점들의 위치를 한 리스트에 넣어준다. 그러면 끝점을 찾아주고, 그 끝점을 기준으로 끝점을 제외한 나머지 점들의 위치를 파악해서, 옮겨주는 작업을 해주었다.
좌표계로 그려보면 알겠지만, 끝점을 원점으로 생각해서, 그 점을 기준으로 1,2,3,4 사분면에 있을때 회전하는 위치를 계산해주었다.
1사분면에 있으면 1사분면의 y축 값은 x축값이 되고, x축의 값은 +y축값이 된다.
2사분면에 있으면 2사분면의 x축값은 +y축값이 되고, y축값은 -x축 값이 된다.
이런식으로 구분을 해서, 각 끝점을 기준으로 움직인 위치를 찾아서 드래곤 커브 리스트에 넣어준다.
여기서 주의 해야할 점은 두가지인데, 문제에 주어진 xy좌표축은 수직방향으로 위로 올라갈수록 y축 값이 줄어드는 것이다.
그리고 두번째는 끝점을 기준으로 뒤에서부터 판별을해야 한다는 것이다.
이렇게 모든 세대를 돌리고 난뒤에 101*101 행렬에 점을 찍어주면 된다. 그리고 마지막으로 네 귀퉁이에 전부 1인 경우에를 세어서 결과로 출력하면 된다.
import sys
input = sys.stdin.readline
N = int(input())
arr = [[0]*101 for _ in range(101)]
dx = [1,0,-1,0]
dy = [0,-1,0,1]
for _ in range(N):
x,y,dire,gener = map(int,input().split())
# dire 0 ->1
# 1->2
# 2->3
# 3->0
move_list = [dire]
arr[y][x] = 1
for _ in range(gener):
temp = []
for i in range(len(move_list)-1,-1,-1):
temp.append((move_list[i]+1)%4)
move_list.extend(temp)
for i in move_list:
nx = x + dx[i]
ny = y + dy[i]
arr[ny][nx] = 1
x,y = nx,ny
result = 0
for y in range(100):
for x in range(100):
if arr[y][x] + arr[y+1][x] + arr[y][x+1] + arr[y+1][x+1] == 4:
result += 1
print(result)좀 더 쉬운 풀이는 다음과 같다.
진행방향만 넣어주는 것이다.
90도 시계방향을 회전하면 다음 진행반향은 현재 진행방향의 +1 의 modulo 4 연산을 해주면 된다.
이렇게 move_list에 넣어주고, 위에서처럼 끝점부터 해서 넣어주면 된다.
그리고 모든 세대를 지난뒤에, 처음시작점에서 진행방향에 맞춰서 점을 찍어주면 된다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 1963 소수 경로 (0) | 2021.03.11 |
|---|---|
| [BOJ/백준] 1504 특정한 최단 경로 (0) | 2021.03.11 |
| [BOJ/백준] 2096 내려가기 (0) | 2021.03.08 |
| [BOJ/백준] 1922 네트워크 연결 (0) | 2021.03.08 |
| [BOJ/백준] 1261 알고스팟 (0) | 2021.03.08 |