오늘의 문제
백준 17825번
https://www.acmicpc.net/problem/17825
문제
주사위 윷놀이
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.
- 처음에는 시작 칸에 말 4개가 있다.
- 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
- 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
- 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.
문제 접근
백트래킹을 통한 탐색
- 백트래킹을 사용하여 각 말의 모든 이동 가능 경로를 탐색하고, 그 중에서 최대 점수를 찾는다.
- 게임판의 각 칸에는 특정한 점수가 있으며, 도착한 위치에 따라 점수를 더해준다.
- 말이 이동할 때 다른 말이 있는 칸으로 이동할 수 없다. 이를 위해 각 말의 위치를 추적하고 이동 가능 여부를 판단.
풀이
1. 게임판과 점수 초기화 (graph와 score 배열)
graph배열: 각 위치에서 다음으로 이동할 수 있는 칸을 정의한 그래프.graph[i]는 위치 i에서 갈 수 있는 다음 칸들의 리스트.- 예를 들어,
[6, 21]과 같은 경우는 해당 위치에서 두 가지 경로로 나뉘는 파란색 화살표와 같은 상황.
score배열: 각 칸에 적혀 있는 점수를 저장.- 점수는 말이 도착한 위치에 따라 추가되며, 특정 위치로 이동하면 그 위치에 해당하는 점수를 더함.
2. 백트래킹 함수 (backtracking())
-
backtracking(loc, result, horse, test)함수는 다음 인자를 받음:loc: 현재 턴 번호.result: 현재까지의 누적 점수.horse: 각 말의 현재 위치.test: 경로를 추적하기 위해 말이 이동한 경로를 기록하는 리스트.
-
재귀 종료 조건:
- 모든 주사위 턴을 완료했으면 (loc >= 10), 현재까지의 누적 점수를 answer와 비교하여 최대 값을 갱신.
-
말 이동 처리:
- 4개의 말 중 하나를 선택하여 이동.
- 말이 파란색 칸에 위치하면 분기하여 파란색 화살표를 따라감.
- 주사위 값만큼 이동한 후, 다음 위치가 다른 말이 있는지 확인.
-
이동한 말 처리:
- 이동할 칸이 다른 말이 없는 경우 이동을 완료.
- 도착한 위치의 점수를 더함.
- 그 후, 다음 턴(loc + 1)으로 진행하기 위해 backtracking()을 재귀 호출.
- 재귀 호출이 끝나면 원래 상태로 돌아와 다른 경우의 수를 탐색.(백트래킹 과정).
3. 결과 출력
최종적으로 얻을 수 있는 최대 점수를 출력합니다.
전체 풀이
graph = [[1], [2], [3], [4], [5], [6, 21], [7], [8], [9], [10], [11, 25], [12], [13], [14], [15], [16, 27], [17], [18], [19], [20], [32], [22], [23], [24], [30], [26], [24], [28], [29], [24], [31], [20], [32]]
score = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 13, 16, 19, 25, 22, 24, 28, 27, 26, 30, 35, 0]
dice = list(map(int, input().split()))
answer = 0
def backtracking(loc, result, horse, test):
global answer
if loc >= 10:
answer = max(answer, result)
return
for i in range(4):
x = horse[i]
# 파란색 칸에서 경로 분기 처리
if len(graph[x]) == 2:
x = graph[x][1]
else:
x = graph[x][0]
# 주사위 수만큼 이동
for j in range(1, dice[loc]):
x = graph[x][0]
# 도착 칸이거나 다른 말이 없는 경우 이동
if x == 32 or (x < 32 and x not in horse):
before = horse[i]
horse[i] = x
test.append(x)
backtracking(loc + 1, result + score[x], horse, test)
test.pop()
horse[i] = before
# 초기화 및 호출
backtracking(0, 0, [0, 0, 0, 0], [])
print(answer)오늘의 회고
35일간 항해 99 알고리즘 스터디를 진행했다. 이번에 느낀 점은 기초도 아직 부족한 실력으로 미들러를 선택해서 찾아보면서 정리도 하고 공부는 되었지만 아직 스스로 풀 자신이 없는 것 같다. 기초부터 더 정리하고 더 연습을 하면 실력이 늘지 않을까! 고생했지만 더 고생하자!
