2701번 - 육각 퍼즐 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 41 | 24 | 22 | 57.895% |
문제
육각 퍼즐이란 정육각형의 꼭짓점과 중심에 원이 그려져 있는 퍼즐이고, 아래 그림과 같이 원이 연결되어 있다. 또, A, B, C, D, E, F로 글자가 새겨져 있는 동전이 아래 그림과 같이 원 위에 놓여 있다. 퍼즐에서 한 번 움직일 때, 동전을 연결된 빈 칸으로 움직일 수 있다.
처음 동전이 섞인 상태로 주어졌을 때, 동전을 아래 그림과 같이 맞추는 최소 이동 회수를 구하는 프로그램을 작성하시오. 처음 상태에서 가운데 칸은 비어있다.
처음 중심 정점은 비어있고 바깥쪽 정점 6 개가 A부터 F의 주어진 순열이 주어졌을 때 원래 ABCDEF 순서로 돌아가게 퍼즐을 푸려고 한다.
퍼즐의 상태는 위의 그림의 A 위치에 있는 동전부터 F까지 차례대로 주어진다. 퍼즐을 움직인 방법을 출력할 때는, 움직인 동전을 출력하면 된다.
예를 들어, FACDBE 퍼즐을 풀 때는 BEFAB로 움직이면 풀 수 있다.
퍼즐의 초기 상태가 주어졌을 때, 이 퍼즐을 푸는 방법을 출력하는 프로그램을 작성하시오. 이때, 움직인 동전의 수를 최소로 해야 한다.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 퍼즐의 초기 상태가 주어진다.
출력
각 테스트 케이스에 대해서 최소 회수를 출력하고 공백을 출력한 뒤, 푸는 방법을 출력한다. 만약, 풀 수 없는 퍼즐이라면 -1을 출력한다.
예제 입력 1
12 FACDBE ABCDEF ADCEFB ADCEBF FEDCBA FEDCAB ECBFAD ECBFDA DCEBFA DCEBAF CBEADF BDEAFC
예제 출력 1
5 BEFAB 0 19 DABFECABFEDBACDEFAB -1 29 EDCBEDFAEDFAEDBCAFBDEFACDEFAB -1 19 CBFACBFACDEFACDEFAB -1 13 CDAFBEDCBEDCB -1 21 DAEBDAEBDCFEBDCABEFAB 16 FAEDBCAFBCAFEDCB
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호