[Baekjoon] 17822번 : 주사위 윷놀이 - Python

Gold 2

17825번: 주사위 윷놀이

아으 머리아퍼.. 읽고 보드판만 잘 짜놓으면 금방 풀수있겠는데? 했는데 

겹치는 칸이 있을 줄이야... 

 

문제 풀이

dfs 문제

2차원 리스트를 만들어서 시작 - 도착까지 멀리 돌아가는 기본(0번)루트와 파란 발판을 밟았을 때 도착으로 갈 수 있는 루트(1, 2, 3번)를 저장했다. 

그리고 기본적인 구현문제 처럼 말의 좌표를 이동시키면 된다. dfs로,, 턴이 10번째가 될 때 return하도록!

 

주의해야 할 것은 형광펜으로 표시한 부분인데 25-40번의 경우는 1, 2, 3번 루트에 모두 존재하기 때문에 인덱스가 달라서 다른 지점으로 인식한다. 이 부분은 따로 조건문을 만들어서 같은 지점으로 판단하도록 해줬다.

30번도 분기점인 경우와 아닌 경우를 구분해야 하는데 30인 경우 첫번째 인덱스가 0인지 확인해 구분해줬다.

 

 

코드

# 보드 만들기
board = [[0] * 20 for _ in range(4)]
board[0] = [2 * i for i in range(1, 21)]
board[1][:8] = [10, 13, 16, 19, 25, 30, 35, 40]
board[2][:7] = [20, 22, 24, 25, 30, 35, 40]
board[3][:8] = [30, 28, 27, 26, 25, 30, 35, 40]

checkli = [[[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, 19]]]

# 말의 위치
p = [[0, -1] for _ in range(4)]
blue, dupli = [10, 20], [25, 30, 35, 40]
dice = list(map(int, input().split()))

maxScore = -1

def dfs(num, s):
    global maxScore

    if num == 10:
        maxScore = max(maxScore, s)
        return

    for i in range(4):
        temp = p[i]
        # 이미 도착한 말이면 옮기지 않음
        if temp == [100, 100]: continue
        ny = temp[1] + dice[num]
        nx = temp[0]

        if ny >= 20 or board[nx][ny] == 0:
            p[i] = [100, 100]
            dfs(num + 1, s)
            p[i] = temp

        else:
            if [nx, ny] not in p:
                # 파랑인 경우 : 30은 두 칸 있기 때문에 따로 정해줘야 함
                if board[nx][ny] in blue or (board[nx][ny] == 30 and nx == 0):
                    nx = board[nx][ny] // 10
                    ny = 0

                # 파랑이 아니면서 [25, 30, 35, 40] 이 칸들은 모든 경로에 존재하기 때문에 따로 확인
                else:
                    check = False
                    if board[nx][ny] in dupli:
                        idx = dupli.index(board[nx][ny])
                        for j in range(len(checkli[idx])):
                            if checkli[idx][j] in p:
                                check = True
                    if check: continue

                if [nx, ny] not in p:
                    p[i] = [nx, ny]
                    dfs(num + 1, s + board[nx][ny])
                    p[i] = temp

dfs(0, 0)
print(maxScore)

 

느낀점

코드가 깔끔하지 못한 기분이 든다.. 

문제 풀다보니 어느새 백준 골드 4가 되었다. 자축!