[BOJ] 17825 - 윷놀이

김우경·2021년 4월 26일
0

삼성기출

목록 보기
29/37

문제링크

17825 - 윷놀이

문제설명

다음과 같은 게임판에서 주사위를 10번 굴려 나온 수 만큼 말을 이동시킨다.

  • 초기 말은 4개 모두 시작칸에
  • 게임판의 화살표 대로만 이동이 가능하다 -> 파란칸에서 이동을 시작하면 파란 화살표로, 이동중이나 파란칸이 아닌 칸에서 시작하면 빨간 화살표를 따라 이동한다.
  • 도착칸에 도착하면 주사위에 나온 수와 상관없이 이동을 마친다
  • 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
  • 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. -> 해당 경우는 고려하지 말라는 뜻
  • 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

문제풀이

저 게임판을 어떻게 저장할지가 관건인 문제인 것같다. 나도 저기서 고민 오래했고,,,

게임판의 저장

게임판은 다음과 같이 board 딕셔너리에 저장했다.
board[i] = [(score, next)] : i번째 칸은 score만큼의 점수를 가지고, 화살표가 가리키는 다음 칸은 next
horses[i] : i번째 말이 위치한 칸 번호

board = defaultdict()
for i in range(21):
    board[i] = [(i*2, i+1)]
board[21] = [(0, -1)] # 도착칸

board[5].append((10, 22))
board[22] = [(13, 23)]
board[23] = [(16, 24)]
board[24] = [(19, 25)]

board[10].append((20, 29)) 
board[29] = [(22, 30)]
board[30] = [(24, 25)]

board[15].append((30, 28))
board[28] = [(28, 27)]
board[27] = [(27, 26)]
board[26] = [(26, 25)]

board[25] = [(25, 31)]
board[31] = [(30, 32)]
board[32] = [(35, 20)]

dfs

dfs를 이용해서 모든 경우에 대해 탐색했다.

def dfs(dice, score):
    global answer
    if len(dice) == 0:
        # 주사위 10번에 대해서 다 돌았으면
        answer = max(answer, score)
        return
    
    for h in range(4):
        if horses[h] != 21:
            x = horses[h]
            # 해당 말 dice[0]만큼 이동 후 얻은 점수 계산
            score_this_turn = move(dice[0], h)
            if score_this_turn < 0:
                continue
            dfs(dice[1:], score+score_this_turn)
            # 이전 상태로 돌리기
            horses[h] = x

말의 이동

말이 이동하는 부분은 다음과 같이 구현했다.

def move(moves, h):
    # h번째말 moves번 이동시키기
    x = horses[h]
    next_pos = 0
    flag = False
    
    # 처음 1칸 이동
    if x in [5,10,15]:
        next_pos = board[x][1][1]
    else:
        next_pos = board[x][0][1]
    
    # 이동한 칸이 도착칸이면
    if next_pos == 21:
        horses[h] = next_pos
        flag = True
    else:
        # moves-1칸 이동
        for i in range(moves-1):
            next_pos = board[next_pos][0][1]
            if next_pos == 21:
                # 이동하다가 도착칸을 만나면
                horses[h] = next_pos
                flag = True
                break
    
    # 현재 말의 상태 갱신 -> 도착한 칸에 다른 말 있는지 검사
    if flag != True:
        for i in range(len(horses)):
            if i != h:
                if horses[i] == next_pos:
                    return -1
        horses[h] = next_pos
                    
    return board[horses[h]][0][0]

전체 코드

import sys
from collections import defaultdict
input = sys.stdin.readline

dice = list(map(int, input().split()))
# board[i]:[(score, next)] -> i번째 칸은 (score 점수, 다음 칸)
board = defaultdict()
for i in range(21):
    board[i] = [(i*2, i+1)]
board[21] = [(0, -1)] # 도착칸

board[5].append((10, 22))
board[22] = [(13, 23)]
board[23] = [(16, 24)]
board[24] = [(19, 25)]

board[10].append((20, 29)) 
board[29] = [(22, 30)]
board[30] = [(24, 25)]

board[15].append((30, 28))
board[28] = [(28, 27)]
board[27] = [(27, 26)]
board[26] = [(26, 25)]

board[25] = [(25, 31)]
board[31] = [(30, 32)]
board[32] = [(35, 20)]

horses = [0 for _ in range(4)]
answer = 0

def move(moves, h):
    # h번째말 moves번 이동시키기
    x = horses[h]
    next_pos = 0
    flag = False
    
    # 처음 1칸 이동
    if x in [5,10,15]:
        next_pos = board[x][1][1]
    else:
        next_pos = board[x][0][1]
    
    # 이동한 칸이 도착칸이면
    if next_pos == 21:
        horses[h] = next_pos
        flag = True
    else:
        # moves-1칸 이동
        for i in range(moves-1):
            next_pos = board[next_pos][0][1]
            if next_pos == 21:
                # 이동하다가 도착칸을 만나면
                horses[h] = next_pos
                flag = True
                break
    
    # 현재 말의 상태 갱신 -> 도착한 칸에 다른 말 있는지 검사
    if flag != True:
        for i in range(len(horses)):
            if i != h:
                if horses[i] == next_pos:
                    return -1
        horses[h] = next_pos
                    
    return board[horses[h]][0][0]

def dfs(dice, score):
    global answer
    if len(dice) == 0:
        # 주사위 10번에 대해서 다 돌았으면
        answer = max(answer, score)
        return
    
    for h in range(4):
        if horses[h] != 21:
            x = horses[h]
            # 해당 말 dice[0]만큼 이동 후 얻은 점수 계산
            score_this_turn = move(dice[0], h)
            if score_this_turn < 0:
                continue
            dfs(dice[1:], score+score_this_turn)
            # 이전 상태로 돌리기
            horses[h] = x

dfs(dice, 0)
print(answer)

소요시간

4시간 ^_ㅠ ;; 최근 풀었던 구현문제중에 젤 어려운드,.,

말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.

이게 대체 먼 소린가 이해가 안가서 다른 블로그를 참고했더니 그냥 이번 턴에서 해당 말은 pass하라는 소리였음

profile
Hongik CE

0개의 댓글