[백준] 15685번: 드래곤 커브 (Python)

 

 

 

 

 

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

15685번: 드래곤 커브

 

 

 

 

 

✅  Solution

• 90도를 어떻게 이동시킬지에 대한 아이디어가 중요한 문제였다. 하지만 난 생각 못하고 풀이를 봐버렸다. 하 너무 어렵
• 예제 1로 예시를 들어보려고 한다.
  • 이동해야 할 방향 4개 (0, 1, 2, 3)을 먼저 생각해 봤다.
  • 0세대 : 0 
  • 1세대 : 0 1
  • 2세대 : 0, 1, 2, 1
  • 3세대 : 0, 1, 2, 1, 2, 3, 2, 1
• 위에서 규칙을 찾아보면 새로 추가된 선분들은 이미 있었던 선분을 뒤집어 + 1 (만약 4 이상이면 0) 방향으로 움직인 다는 것을 알 수 있다.
  • 2세대로 예를 들면 0 1 (이미 존재한 선분) -> 1 0 (뒤집기) -> 2, 1 (1씩 더하기)
• 그럼 규칙대로 추가될 선분들의 방향을 찾아주고 이동시켜 주면 된다. 
• 그리고 전체를 돌면서 네 선분이 모두 있는 (사각형을 만들 수 있는) 것을 카운트해 주면 된다.

 

 

 

 

 

✅  Code

import sys
input = sys.stdin.readline

n = int(input())
graph = [[0] * 101 for _ in range(101)]

# 0, 1, 2, 3 방향
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


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

    curve = [d]
    
    # 추가될 선분의 방향을 찾아줌
    for i in range(g):
        for j in range(len(curve) - 1, -1, -1):
            curve.append((curve[j] + 1) % 4)

    # 범위 내에 있으면 선분 있음을 의미하는 1로 값 재할당해주고 이어서 진행
    for i in curve:
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < 101 and 0 <= ny < 101:
            graph[nx][ny] = 1
            x, y = nx, ny

answer = 0

# 사각형 카운트
for i in range(100):
    for j in range(100):
        if graph[i][j] and graph[i + 1][j] and graph[i][j + 1] and graph[i + 1][j + 1]:
            answer += 1

print(answer)