[백준] 3193 공 - 파이썬 (Python)

백준 3193 공 - 파이썬 (Python)

문제

NxN개의 정사각형 구역으로 이루어진 정사각형 모양의 게임판이 세워져 있다. 각각의 구역은 비어있거나 벽으로 이루어져 있고, 빈 구역 중 하나에는 공이 놓여있다. 이 공은 중력의 영향을 받기 때문에 항상 벽이나 게임판의 바닥 위에 있게 된다.

우리는 게임판을 시계 방향 또는 시계 반대 방향으로 90도 회전시킬 수 있다. 이때 벽과 공도 게임판과 같이 회전하게 된다. 회전이 끝난 후에 공은 중력의 영향을 받아 벽이나 게임판의 바닥을 만날 때까지 떨어진다.

다음은 게임판을 시계 방향으로 회전시킨 후 시계 반대 방향으로 다시 회전시키는 예시이다.

게임판을 주어진 대로 회전시킨 이후의 상태를 출력하시오.

링크

문제 링크: https://www.acmicpc.net/problem/3193

발상

게임판의 크기는 최대 100만이고, 쿼리는 최대 50만개이다.

이것을 매 쿼리마다 실제로 게임판을 회전하고 공을 그에 맞게 떨어뜨리는 과정을 실행하면 정답 처리를 받는 것은 시간적으로 불가능하다. (100만*50만 + 공 떨어뜨리기 횟수)

따라서 다른 방법을 찾아야 한다. 이런 경우, 문제를 해결할 수 있는 한 가지 방법은 쿼리마다 과도한 연산을 하지 않고 미리 구해놓은 무언가를 사용하여 매 쿼리마다 응답만 해주는 형태로 코드를 작성하는 것이다.

1. 게임판은 4가지 형태로 존재할 수 있다. (400만)

2. 게임판의 형태와 좌표에 따라, 최종적으로 떨어지는 자리를 미리 구해서 저장해놓는다 (1번의 4가지 경우 모두, 400만)

3. 공의 첫 위치를 좌표로 저장하고, 게임판에서 지운다.

4. 게임판을 회전하면, 현재 공의 좌표도 그에 맞게 수정하고 2번의 결과에 따라 한 번 더 좌표를 변경한다.

코드