[python] 백준 - 15685. 드래곤 커브 (삼성 SW 역량 테스트 기출 문제)

🤔문제 해결

• G4 | 구현, 시뮬레이션

좌표를 구해서 회전을 시켜가며 구하려고 했지만 도저히 아닌거 같았다.

( 방향이 주어졌는데 처음 1번만쓰고 버리나? 라고 생각했음 )

방향으로 보니 규칙성이 있었다.

• 0세대: 0
• 1세대: 0 | 1
• 2세대: 0 1 | 2 1
• 3세대: 0 1 2 1 | 2 3 2 1

이제 구하는 순서는

• 드래곤 커브하나(한줄)의 방향들 구하기
• 드래곤 커브하나의 시작점을 기준으로 방향에 따라 쭉쭉 좌표써내려가기
• 모든 드래곤 커브를 맵에 표시했다면 네모 구하기

 

💻소스 코드

import sys

input = sys.stdin.readline


def make_curve(x, y, d, g):
    # 좌표로 푸는것이 아니라 규칙을 찾아 진행방향으로 푼다!
    # 진행방향은 지금까지 진행해온 것들을 역순으로 꺼내서 반시계 90도 회전시킨다.
    directions = [d]
    for i in range(g):
        for j in range(len(directions) - 1, -1, -1):
            # 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 0
            directions.append((directions[j] + 1) % 4)
    # print(directions)

    return directions


def set_coordinates(x, y, directions):
    # 진행방향을 구했으면 좌표를 구한다.
    # 전체 크기는 101 x 101
    # 우, 상, 좌, 하
    dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
    maps[x][y] = 1  # 첫 좌표를 표시 안해주면 고장남
    for k in directions:
        x += dx[k]
        y += dy[k]
        maps[x][y] = 1


def get_square():
    cnt = 0
    for i in range(M - 1):
        for j in range(M - 1):
            # i, j를 기준으로 우, 하, 우하 가 1이면 사각형이다.
            if maps[i][j] and maps[i + 1][j] and maps[i][j + 1] and maps[i + 1][j + 1]:
                cnt += 1
    return cnt


if __name__ == '__main__':
    N = int(input())
    infos = [list(map(int, input().split())) for _ in range(N)]

    all_curves = []
    M = 101
    maps = [[0] * M for _ in range(M)]

    for info in infos:
        # 헷갈려서 원래 하던대로 x를 세로, y를 가로로 바꿈
        y, x, d, g = info  # 가로, 세로, 방향, 세대
        directions = make_curve(x, y, d, g)
        set_coordinates(x, y, directions)

        # for rw in maps:
        #     print(rw)
        # print()

    # answer
    answer = get_square()
    print(answer)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

15685번: 드래곤 커브