[파이썬] 백준 17825 : 주사위 윷놀이 (골드2)

[파이썬] 백준 17825 : 주사위 윷놀이 (골드2)

17825번: 주사위 윷놀이

---

문제

---

풀이

0. 방향성 생각

• 완탐 4^10 == 10**6 -> 중간에 조건에 부합하지 않는 경우 탐색x -> 백트래킹
• 맵 구현은 그냥 인덱스 짜서 구현했음...

1. 입력

dice = list(map(int,input().split()))

info = {i:[0,i+1,i+2,i+3,i+4,i+5] for i in range(33)}
info[16] = [0,17,18,19,20,21]
info[17] = [0,18,19,20,21,21]
info[18] = [0,19,20,21,21,21]
info[19] = [0,20,21,21,21,21]
info[20] = [0,21,21,21,21,21]

info[5] = [0,22,23,24,25,31]
info[22] = [0,23,24,25,31,32]
info[23] = [0,24,25,31,32,20]
info[24] = [0,25,31,32,20,21]
info[25] = [0,31,32,20,21,21]

info[10] = [0,26,27,25,31,32]
info[26] = [0,27,25,31,32,20]
info[27] = [0,25,31,32,20,21]

info[15] = [0,28,29,30,25,31]
info[28] = [0,29,30,25,31,32]
info[29] = [0,30,25,31,32,20]
info[30] = [0,25,31,32,20,21]

info[31] = [0,32,20,21,21,21]
info[32] = [0,20,21,21,21,21]


score = {i:2*i for i in range(33)}
score[21] = 0
score[22] = 13
score[23] = 16
score[24] = 19
score[25] = 25
score[26] = 22
score[27] = 24
score[28] = 28
score[29] = 27
score[30] = 26
score[31] = 30
score[32] = 35

• info에는 info[현재위치] = [0,다음위치1, ... , 다음위치5]
• score에는 score[도착위치] = 점수

2. DFS 함수 정의

answer = 0
now = [0]*5

def dfs(stage,s):
    
    global answer
    
    if stage == 10:
        answer = max(answer,s)
        return

    for player in range(1,5):
        if now[player] != 21:
            temp = set(range(1,5))
            temp.remove(player)
            fail = False
            for other in temp:
                if now[other] != 21 and info[now[player]][dice[stage]] == now[other]:
                    fail = True
                    break
            if fail:
                continue

            x = now[player]
            now[player] = info[now[player]][dice[stage]]
            s += score[now[player]]
            dfs(stage+1,s)
            s -= score[now[player]]
            now[player] = x

dfs(0,0)
print(answer)

• 10번 탐색했으면 점수 업데이트
• 도착지점 인덱스가 21이다. 현재 플레이어가 도착점에 있지 않는 경우에 탐색진행
• 1~4번 중 현재 player를 제거하고 나머지 말 3개와 비교한다
• 나머지 말이 도착지점에 없을 때 같은 지점으로 가버리면 불가능 -> 다른 말 이동해야함
• 밑부분은 점수랑 현재 위치 now를 업데이트한다

 

 

---

전체코드

dice = list(map(int,input().split()))

info = {i:[0,i+1,i+2,i+3,i+4,i+5] for i in range(33)}
info[16] = [0,17,18,19,20,21]
info[17] = [0,18,19,20,21,21]
info[18] = [0,19,20,21,21,21]
info[19] = [0,20,21,21,21,21]
info[20] = [0,21,21,21,21,21]

info[5] = [0,22,23,24,25,31]
info[22] = [0,23,24,25,31,32]
info[23] = [0,24,25,31,32,20]
info[24] = [0,25,31,32,20,21]
info[25] = [0,31,32,20,21,21]

info[10] = [0,26,27,25,31,32]
info[26] = [0,27,25,31,32,20]
info[27] = [0,25,31,32,20,21]

info[15] = [0,28,29,30,25,31]
info[28] = [0,29,30,25,31,32]
info[29] = [0,30,25,31,32,20]
info[30] = [0,25,31,32,20,21]

info[31] = [0,32,20,21,21,21]
info[32] = [0,20,21,21,21,21]


score = {i:2*i for i in range(33)}
score[21] = 0
score[22] = 13
score[23] = 16
score[24] = 19
score[25] = 25
score[26] = 22
score[27] = 24
score[28] = 28
score[29] = 27
score[30] = 26
score[31] = 30
score[32] = 35

answer = 0
now = [0]*5

def dfs(stage,s):
    
    global answer
    
    if stage == 10:
        answer = max(answer,s)
        return

    for player in range(1,5):
        if now[player] != 21:
            temp = set(range(1,5))
            temp.remove(player)
            fail = False
            for other in temp:
                if now[other] != 21 and info[now[player]][dice[stage]] == now[other]:
                    fail = True
                    break
            if fail:
                continue

            x = now[player]
            now[player] = info[now[player]][dice[stage]]
            s += score[now[player]]
            dfs(stage+1,s)
            s -= score[now[player]]
            now[player] = x

dfs(0,0)
print(answer)

 

코멘트

맵짜는거만 실수 안하면 뭐..