알고리즘매일매일

https://www.acmicpc.net/problem/17780

17837번 새로운 게임 2 문제(문제 링크)와 거의 똑같은데 조금 더 쉬운 시뮬레이션 문제이다.

(문제 풀이 링크)

이 문제에서는 말이 맨 밑에 있지 않으면 이동시킬 수 없다는 것이 17837번 문제와의 차이점이다.

말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.

벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.

방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.

말을 이동시키기 위해서는 deque배열을 사용하였다.

deque<int> dq[13][13];

위와 같이 deque<int>를 타입으로 가지는 2차원 배열이다.

dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.

이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.

문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.

각 턴에서는 1번 말부터 k번말까지 순차적으로 이동시킨다.

문제 조건에 따라 이동시키기 전에 현재 이동시킬 말이 맨 밑에 있지 않다면 이동할 수 없으므로 바로 리턴한다.

이동시킬 말이 맨 밑에 있다면 이동할 칸의 색깔에 따라서 이동하게 된다.

이동할 칸이

1. 범위를 벗어나거나 파란색 칸인 경우
   • 원래 좌표에서 방향을 반대로 바꾼다.
     1. 다시 한 칸을 이동할 건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼 채로 더 이동하지 않는다.
     2. 그렇지 않다면 이동을 한 건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
2.  흰색인 경우
   • 현재 위치에 있는 말들을 순서대로 (큐의 앞부분부터) 이동할 위치로 이동시킨다.
3. 빨간색인 경우
   • 현재 위치에 있는 말들을 반대 순서로(큐의 뒷부분부터) 이동할 위치로 이동시킨다.

이동을 매번 할 때마다이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고

4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.