[SWEA 19004] 점프 놀이 [C/C++]

문제

SW Expert Academy

---

풀이

입력으로 주어진 정사각형 타일 바닥(board)에 적혀있는 번호에 대해 1부터 K까지 1씩 증가하는 타일로 이동하는 dp문제다.

이동거리는 문제에서 주어진 조건 대로 구할 수 있다.

총 거리의 최솟값을 구해야 하기 때문에 N*N 크기의 dp배열의 모든 요소를 최댓값으로 저장해주자.

 

board를 입력받으며, 타일의 번호( board[i][j] )가 1인 경우에는 시작점 이므로 dp[i][j]를 0으로 해주자.

또한, 타일의 번호가 1~K의 모든 수가 나온다는 보장이 없다. 따로 확인해주자.

 

입력을 다 받은 후, 게임이 가능한지 확인하자. 1 ~  K 번호의 타일들이 존재하는지 확인하면 된다.

만약 1 ~ K 중 하나라도 존재하지 않는다면 게임이 불가능하다. -1 을 출력하고 끝내면 된다.

 

게임이 가능하다면, 현재 탐색 위치에서 다음 탐색 위치까지 거리의 최솟값을 갱신해주면 된다.

단, 타일의 번호가 증가하는 순서대로 갱신을 해주어야 한다. 현재 탐색 대상인 타일 번호가 아니면 건너뛰자.

 

탐색 대상 타일이라면, 현재 위치로부터 N*N 공간에서 다음 타일(ck + 1) 을 재탐색 해주자.

다음 타일을 찾았다면, 해당 타일의 이동 거리를 최솟값으로 갱신해주면 된다.

 

탐색과 갱신이 끝났다면, 타일의 번호가 K인 위치를 찾아 dp에 저장된 이동거리 합의 최솟값을 출력하면 된다.

단, 타일은 여러개 있을 수 있으며 이동거리 또한 각자 다를 수 있다. 가장 작은 합을 출력해주자.

---

소스코드

보기