BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/17825
17825번: 주사위 윷놀이
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
www.acmicpc.net
내가 작성한 코드
from collections import defaultdict, deque
def read_data():
jumps = deque(list(map(int, input().rstrip().split())))
route = deque([x for x in range(2, 42, 2)] + [-1])
route10 = deque([13, 16, 19, 25, 30, 35, 40, -1])
route20 = deque([22, 24, 25, 30, 35, 40, -1])
route30 = deque([28, 27, 26, 25, 30, 35, 40, -1])
change_qs = [-1, route10, route20, route30]
dices = [(0, 0, route.copy()) for _ in range(4)]
return jumps, dices, change_qs
# 1. redundant 케이스 제거
# 2. 말 겹치는 케이스 제거
def select(dices, jump, change_qs):
same_list = [[(1, 4), (2, 3), (3, 4)],
[(1, 5), (2, 4), (3, 5)],
[(1, 6), (2, 5), (3, 6)],
[(1, 7), (2, 6), (3, 7), (0, 20)]]
def same(a, b):
if a == b:
return True
for lst in same_list:
if a in lst and b in lst:
return True
return False
def already_deployed(r, k, i):
if r == -1 and k == -1:
return False
for j in range(4):
_r, _k, _q = dices[j]
if i != j and same((r, k), (_r, _k)):
return True
return False
move_to = defaultdict(list)
for i in range(4):
r, k, q = dices[i]
if (r, k, len(q)) == (-1, -1, 1):
continue
if len(q) <= jump:
r, k, q = -1, -1, deque([-1])
move_to[(r, k)].append((i, q, 0))
continue
k += jump
if r == 0 and (k == 5 or k == 10 or k == 15):
r = k // 5
k = 0
# 겹치는 케이스 제거
if already_deployed(r, k, i):
continue
score = 0
if r != 0 and k == 0:
q = change_qs[r].copy()
score = r * 10
else:
for _ in range(jump):
q = q.copy()
score = q.popleft()
move_to[(r, k)].append((i, q, score))
# redundat case 제거
for k, v in move_to.items():
if k != (-1, -1):
move_to[k] = v[:1]
return move_to
def get_answer(jumps, dices, change_qs):
def push(q, k, move_to, _dices, _jumps, score):
for i, _q, _score in move_to[k]:
_dices = _dices.copy()
_jumps = _jumps.copy()
_dices[i] = (*k, _q)
q.append((_dices, _jumps, score + _score))
q = deque([(dices, jumps, 0)])
mx = -float('inf')
while q:
_dices, _jumps, score = q.popleft()
# debug(_dices, _jumps, score, q)
if not _jumps:
# if mx < score:
# debug(_dices, _jumps, score, q)
mx = max(mx, score)
continue
move_to = select(_dices, _jumps.popleft(), change_qs)
for k in move_to:
push(q, k, move_to, _dices, _jumps, score)
return mx
def test():
print(sum([2,4,6,8,10,13,16,19,25,30]))
def debug(dices, jumps, score, _q):
print("===============================")
for r, k, q in dices:
print((r, k))
print(list(q))
print()
print(f"jumps : {jumps}")
print(f"score : {score}")
print(f"q : {len(_q)}")
print("===============================")
jumps, dices, change_qs = read_data()
print(get_answer(jumps, dices, change_qs))
# test()
- 말 정보
- (위치, 큐)
- 위치 (r, k)
- r
- default = 0
- 10에서 파란 방향 = 1
- 20에서 파란 방향 = 2
- 30에서 파란 방향 = 3 - k
- 움직인 칸의 수
- 파란 방향으로 꺾이면 0으로 초기화
- r
- 남은 칸의 큐 q
- 방향이 꺾이면 다른 큐로 교환
- BFS
- (주사위 정보, 점프 큐, 점수)
- 이동할 말 선택
- 나간 말은 선택하지 않음 (r, k) = (-1, -1)
- 나갈 말은 무조건 선택 len(q) <= jump
- 이동이 겹치는 경우 선택하지 않음
- 모든 주사위에 대해 이동할 위치 탐색 (_r, _k)
- defaultdict(list)에 key=(_r, _k)로 결과 저장, 각 list의 [0]만 이동
- 단, key=(-1, -1)일 경우 리스트 슬라이싱을 하지 않음 - 아래와 같이 겹치는 위치를 주의하여 확인
- ex) 10에서 파란색 방향으로 이동한 7칸 (1, 7) == 20에서 파란색으로 이동한 6칸 (2, 6)
r | 1 | 2 | 3 | 0 |
k | 4 | 3 | 4 | |
k | 5 | 4 | 5 | |
k | 6 | 5 | 6 | |
k | 7 | 6 | 7 | 20 |
다른 사람이 작성한 코드
None
- 강한 구현문제로 다른 코드를 참고하지 않음
기억해야할 것
- 함수화하기
- (r, k)에서 r이 다를 때 말이 겹치는 조건을 디버깅하면서 파악
- "말이 겹친다"를 함수로 바꾸어 빠르게 해결
- 함수로 나눠두지 않으면 나중에 놓친 부분을 바꾸기 힘듦
'코딩테스트' 카테고리의 다른 글
[백준][구현] 새로운 게임 2 (0) | 2022.04.28 |
---|---|
[백준][구현] 원판 돌리기 (0) | 2022.04.28 |
[백준][구현] 모노미노도미노 (0) | 2022.04.27 |
[백준][구현] 청소년 상어 (0) | 2022.04.27 |
[백준][구현] 어른 상어 (0) | 2022.04.27 |