삼성전자 코테 풀이(4) - 주사위윷놀이

문제 설명

알고리즘 공부를 위해 삼성전자 코딩 테스트 문제였던 “주사위 윷놀이” 문제를 풀어보았다.

문제 설명은 아래 사이트를 참고하자

• https://www.acmicpc.net/problem/17825

풀이 방법

주사위 맵을 배열, 링크드 리스트 등의 다양한 자료구조로 구현할 수 있으나

본인은 디버깅 쉽도록 배열을 이용하여 주사위 맵을 구현하였다. 따라서 풀이 방법은 다음과 같다.

1. 윷놀이 맵을 배열로 구현한다
   • 이해하기 쉽도록 아래에 실제로 내가 문제 풀 때 노트에 그린 윷놀이 맵을 첨부한다. 문제 푸는 상황에서 급하게 그린 그림이라 지저분한 점은 양해 해주길..
   • 윷놀이 맵은 9x9크기의 map[9][9]으로 구현하였으며 각 위치에서 빨간색 방향과 파란색 방향에 대한 정보는 red_dir[9][9], blue_dir[9][9]로 구현하였다.
   • 이동 방향은 12시 방향을 0번째로 하여 반시계 방향으로 45도 씩 회전하면서 방향 번호를 할당하였다.

     

2. 말의 위치와 말의 도착 여부를 표현하기 위한 구조체를 정의하여 말 배열을 사용한다.
3. 주사위 10번의 이동을, 한번 이동할 때마다 4개의 말 각각에 대한 DFS를 수행하여 모든 경우의 수를 계산한다.

• 사용 언어: C++
• 알고리즘: 주사위 10번으로 이동할 수 있는 모든 경우의 수를 다 보아야 하므로 DFS 알고리즘으로 모든 경우의 수에 대해 계산하는 Brute Force 문제