17822 원판 돌리기 : https://www.acmicpc.net/problem/17822
Problem
Solve
원판을 T번 회전시킨 후 원판에 적힌 합을 출력하는 문제.
2차원 배열의 행을 원판, 열을 각 위치의 번호로 초기화 시킨후 원판을 회전시키는 함수 turn과 회전 후 원판의 번호의 합을 구하는 함수 count로 문제를 해결한다.
- 2차원 배열의 행을 원판, 열을 각 위치의 번호로 초기화
- circles[원판 번호][해당 원판의 번호 위치]
- T번을 반복하면서 각 회전의 정보를 가지고 원판을 회전시킨다.
- 시계방향으로 회전한다면
(원판의 각 번호의 위치 + 이동거리) % 번호 개수로 위치를 갱신시킨다. - 반시계 방향으로 회전한다면
원판의 번호의 위치 - 이동거리가 양수이면 그값을 그대로 갱신하고 음수라면M + (원판 번호의 각 위치 - 이동거리)
- 시계방향으로 회전한다면
- 2에서 회전한 원판을 통해 조건에 맞게 원판의 번호를 제거 및 합 해준다.
- DFS를 통해 인접해있고 같은 번호를 가진 번호를 제거해준다.
- 이 때 조심해야할 부분은 행의 0번째와 행의 M-1번째는 배열상으로는 떨어져있지만 원판으로 생각하면 연결되어있기 때문에 열의 이동을 계산할때
오른쪽으로 이동한다면 (현재 위치+오른쪽으로 한칸)%M,왼쪽으로 이동한다면 (현재 위치+왼쪽으로 한칸)으로 했을때 음수가 나온다면 M-1로 변경해주어 행의 첫번째 요소와 마지막 요소가 연결되도록 계산해주어야한다.
Code
public class 원판돌리기 {
static int N;
static int M;
static int T;
static int[][] circles;
static int[][] infos;
static int[] dy = {-1,0,1,0};
static int[] dx = {0,-1,0,1};
static int DELETE = 100000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
//원판 저장
circles = new int[N][M];
//회전 정보 저장
infos = new int[T][3];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j=0;j<M;j++){
circles[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<T;i++){
st = new StringTokenizer(br.readLine());
infos[i][0] = Integer.parseInt(st.nextToken());
infos[i][1] = Integer.parseInt(st.nextToken());
infos[i][2] = Integer.parseInt(st.nextToken());
}
int answer = 0;
//T번 회전
for(int i = 0;i<T;i++){
//원판 회전
turn(i);
//회전 후 원판의 번호 합
answer = count();
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
//원판의 번호의 합 구하기
static int count(){
int sum=0;
boolean flag = false;
boolean[][] visit = new boolean[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
//인접하고 번호가 같은 번호를 찾아서 제거
if(!visit[i][j] && circles[i][j] != DELETE){
boolean result = bfs(i,j, visit);
//dfs함수에서 true를 반환한다면 한번이상 인접한 같은 번호를 찾아 제거 했다는 뜻
if(result){
flag = true;
}
}
}
}
//남아있는 숫자의 합과 개수
int numberCount = 0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(circles[i][j] != DELETE){
sum += circles[i][j];
numberCount++;
}
}
}
//인접한 번호가 없어 번호가 삭제되지 않았다면 현재 번호의 평균값을 구해 보다 작은 값은 +1, 보다 큰 값은 -1로 갱신 후 합을 구해 반환한다.
//삭제가 되었다면 남아있는 번호의 합 반환.
if(!flag){
double avg = (double)sum/numberCount;
sum = 0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(circles[i][j] != DELETE){
if(circles[i][j] < avg){
circles[i][j] += 1;
}else if(circles[i][j] > avg){
circles[i][j] -= 1;
}
sum += circles[i][j];
}
}
}
}
return sum;
}
//인접한 같은 번호 찾기
static boolean bfs(int y, int x ,boolean[][] visit){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{y,x});
visit[y][x] = true;
boolean flag = false;
int targetNumber = circles[y][x];
while(!queue.isEmpty()){
int[] current = queue.poll();
for(int i=0;i<4;i++){
int ny = (current[0]+dy[i]);
//해당 원판의 첫번째와 마지막 번호는 연결되어있다.
int nx = (current[1]+dx[i])%M;
if(nx < 0) nx = M-1;
if(ny>=0 && nx>=0 && ny<N && nx<M && !visit[ny][nx] && circles[ny][nx] != DELETE && circles[ny][nx] == targetNumber){
flag = true;
circles[current[0]][current[1]] = DELETE;
circles[ny][nx] = DELETE;
queue.offer(new int[]{ny,nx});
visit[ny][nx] = true;
}
}
}
return flag;
}
//원판 회전
static void turn(int turn){
int[] info = infos[turn];
int x = info[0];
int d = info[1];
int k = info[2];
//x의 배열인 원판 찾기
for(int i=0;i<N;i++){
//x의 배열이 아닌 원판은 패스
if((i+1)%x != 0) continue;
int[] circle = new int[M];
for(int j=0;j<M;j++){
int number = circles[i][j];
if(d == 0){
//시계 방향으로 이동
int rightMove = (j+k)%M;
circle[rightMove] = number;
}else{
//반시계 방향으로 이동
int leftMove = j-k < 0 ? M + (j - k) : j-k;
circle[leftMove] = number;
}
}
circles[i] = circle;
}
}
}
Result
인접한 번호가 원판의 첫번째와 마지막 번호가 붙어있다는 것을 생각하지 못해서 디버깅 하는데 오래걸린 문제. 구현도 약하다..
Reference
내 꿈은 좋은 개발자