[BOJ] 백준 17822 원판돌리기-java

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (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)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키지 전과 일치해야 한다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

문제:https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

풀이

오랜만에 시뮬레이션 문제를 풀었다. 

풀게 된 이유 = 시뮬레이션 문제는 그냥 풀면된다고 생각하고 안풀었다. 그러던 어느날 .. 코딩테스트에서 어려운 시뮬레이션 문제나와서 못풀고 멘붕왔기때문!

이번 문제는 처음보고 쉬워보였다. 그냥 나온대로 하면되는거라고 생각했다. 하지만 생각외로 처리해줘야할 부분이 있었다. 

첫번째, i의 배수 원판을 모두 돌리는 것이다. 나는 i번째 원판만 돌리고 두번이나 제출해서 계속 틀렸다.. 문제 꼼꼼히 읽기..!

두번째, 원판이 여러개라고 가정라고 이차원배열로 풀었는데 문제는 1차원 배열(한 원판)안에서는 0번째와 M-1번째가 이웃한다고 가정하고 범위를 넘어섰을 때 %연산자를 써서 같은 수인지 확인해줘야한다.

세번째, 단순히 나의 위,아래,오른쪽,왼쪽에 같은 수가 있는지만 확인하는 것이 아니다. 원판을 회전시켜놓고 dfs혹은 bfs같은 탐색 법을 통하여 같은 숫자가 모여있으면 전부를 지워야한다.

이 부분들만 처리를 한다면 나머지는 문제에 나와있는대로 풀면된다.

일단 나는 2차원배열에 원판 숫자를 입력받고 회전을 시켰다. rotate 라는 함수가 회전을 시키는데 회전시킬 때는 배열안의 값을 뒤로 밀거나 앞으로 밀면되기때문에 %연산자를 써서 index를 계산한 뒤 새배열을 다시 2차원 배열이 참조하게 했다. 

한 턴에서 회전이 끝나면checkPlate 라는 메서드를 호출한다. 이 메서드는 같은 숫자들이 모여있으면 지우고 지울 수 있는 숫자가 하나도 없다면 문제에 나온대로 평균값을 구하여 계산한다. 

그 외에 위에서 말한 것처럼 같은 숫자들이 모여있는 건 dfs 로 검사하였다. 처리해야할 부분만 위처럼 잘 처리한다면 금방 풀 수 있는 문제라고 생각한다.