풀이
시간복잡도
4^10 개의 중복 순열을 고려해야한다. 이를 완전 탐색할 경우, 2^20 = 1,048,576이기 때문에 시간초과가 나지 않는다. 따라서 dfs를 이용한 완전 탐색을 해야한다. 또한, 문제에서 주어진 조건에 해당하지 않는 것은 백트래킹을 이용하면 시간이 충분하다.
처음 생각했던 아이디어
둘레길과 지름길을 각각 리스트로 만들어주었다. 이후, 둘레길과 지름길의 경우를 각각 나누어서 다음 위치를 계산했다. 이렇게 했을 때 문제점은 중복되는 코드도 많고, 브랜치를 옮겨다니면서 범위를 벗어난 곳과 visited를 처리하기가 까다롭다는 것이다. 그래서 몇몇 테스트케이스에서 오류가 발생했다.
참고한 아이디어
윷놀이판을 1차원 리스트로 표현할 수 있다. 0~21은 둘레길로 쓰고, 22~32는 지름길로 사용한다. 또한, 다음 위치를 가리키는 포인터 리스트 준비한다. 이를 통해, 길에 따라 말이 이동하게 할 수 있다.
구현 과정
-
사전 준비
포인터(p), 비지티드(v), 말의 위치(horse), 해당 지점의 점수 - 리스트
-
dfs
-
현재 위치(ox), 변하는 위치(nx), 움직여야할 칸(move) - 변수
-
지름길로 가는 교차지점일 경우, 위치를 바꿔줌
주사위는 최소 1이상이 나올 것이므로 미리 한칸 이동시켜주는 대신에, 움직여야할 칸의 갯수를 하나 줄여준다.
-
이동했을 때, 21이하이면 둘레길에서 벗어나지 않으므로 한번에 이동시켜준다.
-
21보다 크다면, for 문을 사용하여 한칸씩 이동한다.
포인터를 따라간다.
-
타겟 위치가 도착지점이 아니고 그 위치에 말이 있다면 이 말은 선택하지 않으므로 continue
-
비지티드와 말의 위치 바꿈
-
dfs 재귀
-
비지티드 말의 위치 원래대로 돌려놓음
-
총평
이틀동안 4시간, 3시간이 걸렸던 문제이다. 구현 아이디어를 생각하는 것은 어렵지 않았으나, 처리해야할 사항들이 많아서 구현을 잘못하면 코드가 복잡해진다. 처음 내가 생각했던 아이디어는 코드가 너무 길고 복잡해져서 다른 사람의 풀이법을 참고하여 다시 작성했다.
코드
def play(turn, val):
global answer
if turn == 10:
answer = max(val, answer)
else:
for idx in range(4):
ox, nx, move = horse[idx], horse[idx], dice[turn]
if nx == 5 or nx == 10 or nx == 15:
nx = p[nx]
move -= 1
if nx + move <= 21:
nx += move
else:
for _ in range(move):
nx = p[nx]
if v[nx] and nx != 21:
continue
v[ox], v[nx], horse[idx] = False, True, nx
play(turn+1, val+values[nx])
v[ox], v[nx], horse[idx] = True, False, ox
dice = list(map(int,input().split()))
p = [i+1 for i in range(33)]
horse = [0] * 4
v = [False] * 33
p[5], p[10], p[15] = 22, 25, 27
p[21] = 21
p[22],p[23],p[24] = 23, 24, 30
p[25], p[26] = 26, 30
p[32] = 20
values = [i*2 for i in range(33)]
values[0] = values[21] = 0
values[22],values[23],values[24] = 13, 16, 19
values[25],values[26] = 22, 24
values[27], values[28], values[29] = 28, 27, 26
values[30], values[31], values[32] = 25, 30, 35
answer = 0
play(0,0)
print(answer)