알고리즘 풀이/백준(Boj)
백준(BOJ) 16959번 체스판 여행 1
100win10
2019. 12. 26. 02:30
문제 : https://www.acmicpc.net/problem/16959
16959번: 체스판 여행 1
크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, 비숍, 룩이다. 가장 먼저 1이 적혀있는 칸에 말 하나를 놓는다. 그 다음, 1, 2, ..., N2 순서로 이동시키려고 한다. 먼저, 1에 나이트, 비숍, 룩 중 하나를 놓는다. 그 다음, 말을 이동시켜서 2가 적힌 칸으로 이동시킨다. 1에서 2로 이동시킬 때,
www.acmicpc.net
풀이 :
중복을 저장하는 d배열을 애초에 4차원 배열로 만들어서 처리하자.
d [y][x][n*n까지의 수-1][0 or 1 or 2]이다. 이때 0 1 2는 나이트인지 비숍인지 룩인지를
나타낸다. 처음에는 우선 나이트일때 비숍일 때 룩일 때 세 가지 다 경우 다 큐에 넣어 준다.
좌표가 n*n-1을 밟았다면 최솟값을 갱신한다. 그 외에는 가만히 말을 바꾸는 경우, 나이트의 탐방
경우, 비숍의 탐방 경우, 룩의 탐방 경우를 큐에 모두 넣어준다.
코드 ( C++ )
