[백준 17825] 주사위 윷놀이 - Python

Algorithm

순열, 시뮬레이션

Logic

주사위를 10번 던지는데, 각 주사위마다 어떤 말을 옮길지 결정해야하므로, 중복순열을 만들었다. -> 개수: (말 개수 = 4)^10개

diceMap: 각 노드에서 연결된 다음 노드번호를 저장하는 adj 리스트

diceScore: 각 노드에 해당하는 포인트를 저장하는 리스트

visited: 말들이 위치한 곳을 나타내는 리스트

• makePermutation(now, goal, arr): 중복 순열을 만드는 함수

  하나의 중복순열이 완성되면 getScore함수를 통해 그 경우에 얻는 score을 반환받는다.

• getScore(arr, diceInfo)

  arr: 각 주사위를 던질 때마다 옮길 말의 정보가 담긴 리스트

  diceInfo: 현재 0~3번 말이 있는 위치를 저장하는 리스트

  주사위를 10번 던질 때마다, 그 때의 말의 위치인 nowLoc과 옮길 횟수인 nowCnt를 얻는다. 옮길 횟수만큼 반복문을 돌면서 말의 위치를 계속 이동시킨다. 이 때 "도착"지점에 오면, 더 이상 이동하지 않으므로 반복문을 종료한다. 계속 이동할 때마다 nowLoc을 갱신해준다.

  주의할 점은 말의 시작지점이 5, 10, 15인 경우이다. 이때는 파란색 경로로 이동해야하므로

  if len(diceMap[nowLoc]) == 2 and c == 0:
      look = 1
  else:
      look = 0

  이를 통해 어느 경로로 갈 지 지정해준다.

  이동이 끝나면, 말을 놓을 새로운 위치에 기존의 말들이 위치하고 있는지 확인해야한다. 이는 visited 리스트를 통해 가능하다. 만약 기존의 말들이 있다면, 놓을 수 없으므로 0을 return 한다.

  놓을 수 있는 위치라면, score을 올려주고 말의 원래 위치의 visited는 False로, 말의 새로운 위치의 visited는 True로 바꿔준다.

Review

걸린시간: 55분(두번째 풀이 기준)

dictionary를 사용하는 첫번째 풀이방법으로는 도저히 해결이 안돼서,, 결국 그래프를 만들고, 각 노드에 해당하는 포인트를 따로 리스트에 저장하여 풀이하였다.

처음부터 직관적이고 간단한 풀이법을 선정해서 풀어야하는데 ㅜ ㅜ 실제로 시험때 완전 어렵고 잘못된 방식으로 풀이를 시작하믄 큰일날 것 같다

더 열심히 해야겠다 !!!

 

Code

def getScore(arr, diceInfo):
    score = 0
    for i in range(10):
        nowLoc = diceInfo[arr[i]]
        nowCnt = sequence[i]
        # flag = False
        for c in range(nowCnt):
            if nowLoc == 32:  # 마지막 도착
                # flag = True
                break
            if len(diceMap[nowLoc]) == 2 and c == 0:
                look = 1
            else:
                look = 0
            nowLoc = diceMap[nowLoc][look]

        if nowLoc != 32 and visited[nowLoc]:
            return 0
        # if not flag:
        score += diceScore[nowLoc]
        visited[diceInfo[arr[i]]] = False
        diceInfo[arr[i]] = nowLoc
        visited[diceInfo[arr[i]]] = True

    return score


def makePermutation(now, goal, arr):
    global maxScore
    global visited

    if now == goal:
        diceInfo = [0, 0, 0, 0]
        visited = [False for _ in range(33)]
        maxScore = max(maxScore, getScore(arr, diceInfo))
        return

    for i in range(4):
        arr[now] = i
        makePermutation(now + 1, goal, arr)


diceMap = [[] for _ in range(32)]
diceScore = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 13, 16, 19, 22, 24, 28, 27, 26, 25, 30, 35, 0]
visited = [False for _ in range(33)]
sequence = [int(x) for x in input().split()]
maxScore = 0

for i in range(20):
    diceMap[i].append(i + 1)

diceMap[5].append(21)
diceMap[21].append(22)
diceMap[22].append(23)
diceMap[23].append(29)
diceMap[10].append(24)
diceMap[24].append(25)
diceMap[25].append(29)
diceMap[15].append(26)
diceMap[26].append(27)
diceMap[27].append(28)
diceMap[28].append(29)
diceMap[29].append(30)
diceMap[30].append(31)
diceMap[31].append(20)
diceMap[20].append(32)

makePermutation(0, 10, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
print(maxScore)