[BOJ] 15685번 드래곤 커브 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

문제의 아이디어는 생각보다 금방 떠올렸다. 직접 예시를 적어보며 하면 규칙을 발견할 수 있다.

x,y 좌표 방향이 평소 다른 문제를 풀었을때의 방향과 거꾸로 주어져서 조금 더 생각해야 했다. 처음 문제를 읽을때부터 파악했어야 하는데 늦게 파악해서 삽질을 조금 했다.

• 추가로 문제에서 점을 기준으로 하는지 면적을 기준으로 하는지 확실히해서 접근해야 혼란이 없다는걸 느꼈다. 이번 문제의 경우 면적이 아닌 점을 기준으로 접근해야 했다.

# ! x,y 좌표 평소 풀던 방향과 반대임
DIRECTIONS = [(1, 0), (0, -1), (-1, 0), (0, 1)]  # 오른쪽, 위, 왼쪽, 아래


def get_dir_idxs(start_dir_idx, generation):
    dir_idxs = [start_dir_idx]
    for _ in range(generation):
        dir_idxs += list(map(lambda x: (x + 1) % 4, dir_idxs[::-1]))  # 뒤집어서
    return dir_idxs


visited = [[False] * 101 for _ in range(101)]  # 커브 놓이면 True로(점 기준)
N = int(input())
for _ in range(N):
    x, y, d, g = map(int, input().split())
    visited[x][y] = True
    dir_idxs = get_dir_idxs(d, g)
    for dir_idx in dir_idxs:
        dx, dy = DIRECTIONS[dir_idx]
        x, y = x + dx, y + dy
        visited[x][y] = True

ans = 0
for i in range(100):
    for j in range(100):
        if visited[i][j] and visited[i + 1][j] \
        and visited[i][j + 1] and visited[i + 1][j + 1]:
            ans += 1

print(ans)