[백준 15685번] 드래곤 커브

n = int(input())

area = [[0]*101 for _ in range(101)]

data = [list(map(int,input().split())) for _ in range(n)]

answer = 0

dx = [1,0,-1,0]
dy = [0,-1,0,1]

for x,y,d,g in data:

    routes = [d]
    area[x][y] = 1

    for i in range(g):
        for j in range(len(routes)-1,-1,-1):
            routes.append((routes[j]+1)%4)

    for route in routes:
        nx, ny = x + dx[route], y + dy[route]
        area[nx][ny] = 1
        x, y = nx, ny

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

print(answer)

이번 문제는 각 입력 값마다 시작 x좌표, y좌표가 주어지고 이동하는 방향과 이동 횟수가 주어졌을 때 모든 경로를 이동한 후의 결과 값을 확인하는 문제이다.

 

처음에 이 문제를 접근할 때는 '끝점을 기준으로 90도 회전시킨다'라는 멘트 때문에 2차원 배열을 어떻게 하면 회전시킬 수 있을까 하고만 고민해 보았는데, 생각보다 공식이 잘 도출되지 않아서 다른 사람의 풀이를 참고하였다.

 

문제풀이는 생각보다 단순했다. 처음 시작 방향을 임의로 0으로 지정했을 때, 세대가 지나면 지날수록 다음 세대가 가지는 방향은 다음과 같다.

 

0세대 : 0

1세대 : 0 / 1

2세대 : 0 1 / 2 1

3세대 : 0 1 2 1 / 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 / 2 3 0 3 2 3 2 1

 

즉, 전 세대의 정보를 뒤집어 거기에 1을 더해주면 된다. 4면 다시 처음인 0으로 돌린다. ⭐️

 

따라서 위 규칙에 따라 모든 세대의 방향을 구해준 뒤, 모든 드래곤 커브의 경로를 1로 표시해주면 문제를 간단하게 풀 수 있었다.

 

이번 문제는 문제에서 주어진 설명에 정신이 팔려서 입력 값과 방향성에 대한 패턴을 인지하지 못한 채 엉뚱한 방향으로 구현을 시도하게 되었었다. 그리고 문제에서 주어진 조건을 제대로 인지하지 않고 평소 2차원 배열 이동방식으로 구현하다보니 잘못된 답이 나오기도 하였다.

 

배운 점 및 느낀 점

1. 로직이나 패턴이 생각보다 잘 도출되지 안된다면, 문제에서 주어진 입력 값과 연관지어서 새로운 패턴을 찾아보도록 하자.
2. 평소에 풀던 방식이 익숙하다고 그대로 풀지말고, 문제에서 주어진 조건(x / y의 범위, 좌표의 이동 방향 등)을 꼼꼼하게 읽어보자.