A. 문제설명
17825번: 주사위 윷놀이
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 �
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 아래와 같은 윷놀이 판과 말 4개가 주어짐
2. 각 말들은 화살표가 주어진 위치로만 이동이 가능하며, 파란색 화살표가 있는 위치에 도달할 경우 파란색 화살표가 가리키는 방향으로 이동
3. 게임은 10개의 턴으로 매 턴마다 주사위를 굴려 각 말들을 이동시키고, 말들은 다른 말이 있는 칸에는 이동할 수 없음
4. 말이 이동을 마칠때마다 해당 칸의 점수가 추가됨
5. 주사위에서 나올 수 10개를 미리 알고 있을 때, 말들을 이동시켜 최대로 얻을 수 있는 점수를 구하라
B. 접근법
시뮬레이션 + DFS
맨 처음 해당 문제에 대해서 인코딩을 링크드리스트의 형태로 생각했으나, DFS의 구현이 까다로워져서 쉽지 않았다. 여러 방법을 고민하다가 아래 링크의 풀이를 찾게 되었는데, 매우 간결한 방식으로 윷놀이 판을 인코딩하여 문제를 해결할 수 있었고 해당 방법을 차용하여 문제풀이를 따라 풀었다.
[ 백준 17825 ] 주사위 윷놀이 (C++)
[문제보기] [해결과정] 1. 윷놀이 판을 구현 (map 초기화/설정) -> 해당 노드에 다음 이동할 노드 번호를 저장 (map 배열) -> 방향 전환이 되는 노드를 따로 관리 (turn 배열) -> 각각의 노드의 점수를 ��
haejun0317.tistory.com
기본적으로 윷놀이 판에서 주어진 점수판 외에 새로 인덱스를 주어지고, 각 말들의 전환지점과 윷놀이 판의 말들의 존재여부를 확인하는 배열을 추가로 구현하여 사용하였다. 그 외에는 기본적인 DFS 형태의 구현 방식을 사용하였고, 이전 말의 위치와 현재 말의 위치를 저장하여 다음 Depth의 DFS 재귀호출에 들어갔다가 나와서 원복하는 형태의 구현방식을 채택하였다.
C. 풀이
1. 윷놀이 판의 인덱스 및 점수판 초기화
2. DFS 함수 탐사 시작하며 초기 말의 위치 저장
3. 파란색 화살표 지점 도달시 방향 전환
4. 현재 위치가 전환점인지 먼저 확인해서 방향 바꿔놓고, 이동 시작
5. 남은 이동횟수만큼 칸 이동
6. 도착위치가 아닌데, 해당 위치에 말이 있다면 못 놓음
7. 이동가능할 시, 해당 칸에 체크하고 점수추가해서 재귀 호출
8. Depth가 10까지 도달하여 모든 이동 완료시 해당 점수를 최대와 비교하여 업데이트
D. 내 코드