백준 15685번 드래곤커브 삼성SW역량테스트 (Python)

백준 15685번 문제 바로가기

문제 이해

드래곤 커브라는 모형이 있다.
예를 들어 방향이 오른쪽으로 시작하는 드래곤 커브는 아래와 같다.


입력에 N개의 드래곤 커브가 주어지고
각각의 드래곤 커브의 시작점, 세대, 방향이 주어진다.
이 때 100X100의 지도에 드래곤 커브를 칠하고 1X1의 정사각형의 각 꼭짓점이 모두 드래곤 커브가 칠해진 경우의 개수를 구한다.

문제 접근

이 문제는 정해진 드래곤 커브를 칠해야 하는 문제라고 생각했다.
따라서 3가지로 구분했다.

• 방향에 따른 드래곤 커브를 생성하기
• 생성된 드래곤 커브를 지도에 (pan)에 칠하기
• 정사각형 개수 구하기

방향에 따른 드래곤 커브를 칠하기 위해 DP를 사용했다.
처음에는 실제 적용될 좌표를 넣어서 DP를 생성하려했다.
회전시켜야 하는 기준점을 기준으로 지금까지 생성된 좌표의 차이를 (dx,dy)라 할때 90도 회전시키면 (-dy,dx)이기 때문에 이런 방식으로 진행하려고 했었다. 하지만 많이 복잡해졌고 더 쉬운 방법으로이 있을 것이라는 생각이 들어서 처음부터 다시 접근했다.

주어진 입력의 세대와 방향에 따라 dp를 실행해 드래곤 커브를 생성했다. dp[i]는 dp[i-1]를 가지고, dp[i-1]의 요소에 각각 1을 더해 (90도 회전을 표현하기 위해) 추가하는 형태이다. 좌표를 저장하는 것이 아니라 방향을 저장하는 dp를 생성한 것이다. 방향에 1을 더하면 90도 회전하기 때문에 이게 정답이라고 생각했다.

이렇게 생성된 드래곤 커브를 지도에 칠하는데 이는
dx = [1, 0, -1, 0]
dy = [0, -1, 0 ,1] 로 x와 y를 갱신하면서 칠해주었다.

마지막으로 지도를 처음부터 확인하면서 정사각형의 개수를 구한다.

문제 해결

입력을 받고 dp를 생성하는 모습이다.
현재 입력받은 좌표에 1을 넣어두어 칠했다는 표시를 하고 초기값 dp[0]에 d를 넣어 시작하는 방향을 지정해주었다.
그 이후에 주어진 입력의 세대까지 dp를 생성해 계산해주었다. dp[i-1]의 값을 dp[i]에 넣어두고 dp[i-1]의 요소들에 1을 더해주면서 4로 나눈 나머지를 저장했다.
이렇게 되면 길이가 1이고 방향이 dp[i]의 요소들인 드래곤 커브가 전부 저장된다.

x,y,d,g = map(int,sys.stdin.readline().split())

    pan[y][x] = 1
    dp = [[d],[],[],[],[],[],[],[],[],[],[]]
    for i in range(1,g+1):
        for j in range(len(dp[i-1])):
            dp[i].append(dp[i-1][j])
        for k in range(len(dp[i-1])-1,-1,-1):
            dp[i].append((dp[i-1][k]+1)%4)

이렇게 저장된 dp에 필요한 세대인 g를 확인한다.
dp[g]에는 g세대의 드래곤 커브의 방향이 들어가 있는데, 길이가 1이기 때문에 x,y에 방향을 더해주면서 이동한다. 이동할 때마다 pan에 1을 칠해주었다.

dx = [1, 0, -1, 0]
dy = [0, -1, 0 ,1]
 for t in dp[g]:
        x += dx[t]
        y += dy[t]
        pan[y][x] = 1

최종적으로 정사각형의 개수를 구하기 위해서 이중 for문으로 하나씩 확인해주었다.

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

제출 코드

from collections import deque
import sys
# 방향에 따른 드래곤 커브를 생성하기 
# 생성된 드래곤 커브를 지도에 (pan)에 칠하기
# 정사각형 개수 구하기
pan = [[0] * 101 for _ in range(101)]
# 0: 우 1: 상 2: 좌 3: 하
# 우로 시작하는 dp

N = int(sys.stdin.readline())
dx = [1, 0, -1, 0]
dy = [0, -1, 0 ,1]
for _ in range(N):
    x,y,d,g = map(int,sys.stdin.readline().split())

    pan[y][x] = 1
    dp = [[d],[],[],[],[],[],[],[],[],[],[]]
    for i in range(1,g+1):
        for j in range(len(dp[i-1])):
            dp[i].append(dp[i-1][j])
        for k in range(len(dp[i-1])-1,-1,-1):
            dp[i].append((dp[i-1][k]+1)%4)
    for t in dp[g]:
        x += dx[t]
        y += dy[t]
        pan[y][x] = 1
answer = 0
for i in range(100):
    for j in range(100):
        if pan[i][j] == 1 and pan[i + 1][j] == 1 and pan[i][j + 1] == 1 and pan[i + 1][j + 1] == 1:
            answer += 1
print(answer)