[백준][구현] 주사위 윷놀이

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

17825번: 주사위 윷놀이

 

내가 작성한 코드

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으로 초기화
  • 남은 칸의 큐 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이 다를 때 말이 겹치는 조건을 디버깅하면서 파악
  • "말이 겹친다"를 함수로 바꾸어 빠르게 해결
  • 함수로 나눠두지 않으면 나중에 놓친 부분을 바꾸기 힘듦