[백준] 15685번 (python 파이썬)

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

 

구현, 시뮬레이션 문제이다.

 

여기서 중요한것은 일단 x, y좌표가 바뀐것이고

 

이전 드래곤 커브에서 90도를 돌린 것을 어떻게 붙일것인지?

 

이것만 금방 생각한다면 쉽게 풀 수 있다. ( 근데 어떻게 생각하냐.... ㄷ)

 

우선 방향을 보면

0 : →

1 : ↑

2 : ←

3 : ↓

인 것을 확인할 수 있는데

 

→ 에서 다음 붙일 것이

이전 드래곤 커브에서 90도 돌려서 끝점에 붙여야 하는것은 ↑ 이다.

 

 

즉 이전 드래곤 커브 선을 거꾸로 확인하면서 90도 돌리며 추가해주면 된다.

 

다음 2세대 드래곤 커브 만드는 것을 보자

 

이 다음 붙일 드래곤 커브는 

이건데 

이전 드래곤 커브를 거꾸로 한 선씩 확인하면서 90도 돌리면 된다.

 

 

 

방향을 확인해보자

보면 이전 커브에 +1된 방향이 추가된다.

 

그러면 필요한 것이 커브에 대한 리스트이다

0세대 선의 개수는 2^0

1세대 선의 개수는 2^1

2세대 선의 개수는 2^2

......

 

위의 드래곤 커브로 예를 든다면

0세대 드래곤 커브 = [0]

1세대 드래곤 커브 = [0, 1]

2세대 드래곤 커브 = [0, 1, 2, 1] 이된다.

 

커브 리스트를 만들었으면

이제 처음 좌표에서 커브리스트의 방향들을 더해가면된다.

 

n = int(input())

graph = [[0] * 101 for _ in range(101)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for i in range(n):

    y, x, d, g = map(int, input().split(' '))
    graph[x][y] = 1

    # 커브 리스트 만들기
    curve = [d]
    for j in range(g):
        for k in range(len(curve) - 1, -1, -1):
            curve.append((curve[k] + 1) % 4)

    # 드래곤 커브 만들기
    for j in range(len(curve)):
        x += dx[curve[j]]
        y += dy[curve[j]]
        if x < 0 or x >= 101 or y < 0 or y >= 101:
            continue

        graph[x][y] = 1

answer = 0
for i in range(100):
    for j in range(100):
        if graph[i][j] == 1 and graph[i + 1][j] == 1 and graph[i][j + 1] == 1 and graph[i + 1][j + 1] == 1:
            answer += 1

print(answer)