A. 문제설명
17822번: 원판 돌리기
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 반지름이 각기 다른 N개의 원판이 주어짐. 각 원판에는 M개의 정수가 적혀짐
2. 각 원판은 1,2, ... ,N번째 원판까지 안쪽부터 바깥쪽으로 끼워짐
3. 각 원판의 엔트리는 (i, j)와 같이 나타나며, 그 규칙은 아래와 같음
(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)4. 이렇게 주어진 T의 배수번째 원판들을 시계/반시계 방향으로 K만큼 회전
5. 회전 후에, 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾음
6. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지움
7. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더함
8. 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하라
B. 접근법
시뮬레이션 + BFS
먼저 M개의 정수가 적힌 N개의 원판을 disc[N][M]으로 인코딩할 수 있다. 원판형태의 데이터 구조라고 생각하면 복잡하지만, 문제에서 이용하고자 하는 건 Circular한 형태(M-1의 엔트리가 0의 엔트리와 이어지는)의 특징외에는 2차원 배열과 다를 것이 없다.
그리고 T의 배수번째 원판들을 시계/반시계 방향으로 K만큼 회전하는 함수를 각각 구현한다. - rotate_cw()/rotate_ccw()
이후, 주변에 인접한 같은 수들을 모두 찾아 지워야 하는데, BFS를 이용하도록 하자. 그러나 일반적인 2차원 배열에서의 너비우선탐색이 아닌 Circular한 데이터타입이라는 점을 염두하자. 그래서 아래와 같이 55번째 라인을 보면, y에 대한 인덱싱이 M-1<->0으로 서로 이동할 수 있도록 따로 처리되어 있다.
// 일반적인 BFS로 탐사할 경우 Circular 형태의 원형 구조를 탐사하지 못한다.
// 그래서 아래와 같이 M-1<->0의 인덱스가 서로 탐사할 수 있도록 y의 인덱싱 처리를 한다.
int nny = (ny+dy[i]+M)%M;
if(available(nx+dx[i], nny) && !visit[nx+dx[i]][nny] && disc[nx+dx[i]][nny]!=0 && disc[nx+dx[i]][nny]==num) {
if(len == 0) disc[nx][ny] = 0;
bfsQ.push(QSTRUCT{nx+dx[i], nny, len+1});
}
이제, 회전 및 같은 수를 제거한 원판들에 대해 후처리로 같은 수가 없었으면 평균 자료형 캐스팅을 조심하여 원판 적힌수의 평균을 구하고, 평균보다 큰수는 1빼고, 작은수는 1더해주면 된다.
C. 풀이
1. 번호판 x-배수번호의 원판을 d(0:시계,1:반시계)방향으로 k칸 회전 - rotate_cw()/rotate_ccw()
2. 원판에 수가 남아있으면 인접하면서 같은수를 찾음
3. 인접동일수가 있으면 모두 지움(BFS)
4. 이때, 일반적인 BFS로 탐사할 경우 Circular 형태의 원형 구조를 탐사하지 못하므로 M-1<->0의 인덱스가 서로 탐사할 수 있도록 y의 인덱싱 처리
5. 없으면 원판 적힌수의 평균을 구하고, 평균보다 큰수는 1빼고, 작은수는 1더함(평균 자료형 캐스팅 조심)
6. 최종적으로 원판에 적힌 수의 합 반환
D. 내 코드
