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

문제 출처

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

15685번: 드래곤 커브

 

 

 

 

---

 

풀이 및 코드

 

해당 문제의 핵심은 "드래곤 커브를 어떻게 구현할 것인가" 이다. 필자는 기존의 방향들을 역순으로 꺼내 반시계 방향돌리는 방식으로 구현했다. 이렇게만 말하면 이해가 되지 않을 것이다. 예시로 살펴보자. 문제에서 소개되었던 예시이다. 

 

 

2세대 드래곤 커브에서는 0, 1 순서로 진행이 되었다. 3세대로 넘어오면서 1을 반시계로 회전시켜 2로 0을 반시계로 회전시켜 1로 변환해 추가해 주었다. 즉 기존의 방향들을 역순으로 반시계 회전한 뒤 기존의 방향들에 추가해주면 된다. 

 

코드는 다음과 같다. 기존의 드래곤 커브는 hist라고 하였을 때 역순으로 반시계 회전한 뒤에 _next에 넣고 hist를 업데이트 해준다. 마지막 세대에 관해 진행한 후에 hist에 맞춰 board를 업데이트 해주었다.

 

# 기존의 드래곤 커브에 맞추어 역순으로 반시계 회전 후 업데이트
hist = [d]
for _ in range(g):
    _next = []
    for d in reversed(hist):
        nd = d + 1 if d < 3 else 0
        _next.append(nd)
    hist += _next

# 계산된 드래곤 커브에 맞추어 board에 체크
board[y][x] = 1
for h in hist:
    y, x = y + dy[h], x + dx[h]
    board[y][x] = 1

 

 

 

---

 

전체코드

 

 

 

 

 

 

 

 

 

 

 

해당 문제는 삼성 기출 문제로 solved.ac에서 골드4에 배치되어 있다.