[백준 17822] 원판 돌리기 - JAVA

원판 돌리기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	9516	3181	1966	29.693%

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 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번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 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번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

예제 입력 1 복사

xxxxxxxxxx
4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1

예제 출력 1 복사

xxxxxxxxxx
30

원판의 초기 상태는 다음과 같다.

x1 = 2, d1 = 0, k1 = 12번, 4번 원판을 시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 2 복사

xxxxxxxxxx
4 4 2
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3

예제 출력 2 복사

xxxxxxxxxx
22

예제 1에서 이어진다.

x2 = 3, d2 = 1, k2 = 33번 원판을 반시계 방향으로 3칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 3 복사

xxxxxxxxxx
4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2

예제 출력 3 복사

xxxxxxxxxx
22

예제 2에서 이어진다.

x3 = 2, d3 = 0, k3 = 22, 4번 원판을 시계 방향으로 2칸 돌린 후	인접하면서 수가 같은 것이 없다.따라서, 평균 22/6 보다 작은 수는 +1, 큰 수는 -1 했다.

예제 입력 4 복사

xxxxxxxxxx
4 4 4
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
3 1 1

예제 출력 4 복사

xxxxxxxxxx
0

예제 3에서 이어진다.

x4 = 3, d4 = 1, k4 = 13번 원판을 반시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 5 복사

xxxxxxxxxx
4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2

예제 출력 5 복사

26

 

 

풀이

엄청 고생해서 풀었습니다...

 

문제에서 평균을 계산 할 때 int형으로 하면 안되고 double형으로 처리를 해줘야 합니다.

 

저는 bfs, dfs를 이용해서 풀지 않았고 2중 반복문으로 풀었습니다.

set을 이용해서 같은 값이 있는 좌표들을 다 담아주고 (중복된 좌표를 받지 않기 위해 set으로 했습니다)

그 후 0으로 바꿔주었습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n,m,t,x,d,k;
    static int arr[][];
    static HashSet<Node>set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] tt = br.readLine().split(" ");
        
        n = Integer.parseInt(tt[0]);
        m = Integer.parseInt(tt[1]);
        t = Integer.parseInt(tt[2]);    // 회전횟수
        
        arr = new int[n+1][m+1];
        
        for(int i=0; i<n; i++) {
            tt = br.readLine().split(" ");
            for(int j=0; j<tt.length; j++) {
                arr[i+1][j+1] = Integer.parseInt(tt[j]);
            }
        }
        
        
        while(t-->0) {
             tt = br.readLine().split(" ");
             x = Integer.parseInt(tt[0]);   // 번호가 x의 배수인 원판을 회전
             d = Integer.parseInt(tt[1]);   // 회전시킬 방향 0 : 시계  1: 반시계
             k = Integer.parseInt(tt[2]);   // 몇칸 회전 시킬지
             
             int tmp = x;
             while(tmp<=n) {
                 for(int i=0; i<k; i++) {
                     rotate(tmp);
                 }
                 tmp+=x;
             }
​
             find_same();       // 지울수 있는지 여부 파악
​
             if(set.size()!=0) {    // 지울수 있는게 있으면 지우기
                 for(Node a : set) {
                     arr[a.x][a.y] = 0;
                 }
             }
             else {
                 calculate();
             }
        }
​
        int ans =0;
    
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                ans+=arr[i][j];
            }
        }
        
        System.out.println(ans);
        
    }
    public static void print() {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                System.out.print(arr[i][j]+" ");
                 
            }
            System.out.println();
        }
    }
​
    public static void calculate() {
        double sum = 0;
        double cnt =0;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(arr[i][j]!=0) {
                    sum+=arr[i][j];
                    cnt++;
                }
            
            }
            
        }
        if(cnt!=0) {
            sum/=cnt;
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(arr[i][j]==0) {
                    continue;
                }
                if(sum > arr[i][j]) {
                    arr[i][j]++;
                }
                else if(sum < arr[i][j]) {
                    arr[i][j]--;
                }
            }
        }
    }
    public static void find_same() {
        set.clear();
        // 같은 원판끼리 인접하는것
        for(int i=1; i<=n; i++) {
            for(int j=1; j<m; j++) {
                if(arr[i][j]==0) {
                    continue;
                }
                if(j==1) {  // (i,1) 과 (i,m)은 인접하다를 처리하기 위해
                    if(arr[i][1] == arr[i][m]) {
                        if(arr[i][1]==arr[i][m]) {
                            set.add(new Node(i,1));
                            set.add(new Node(i,m));
                        }
                    }
                    
                }
                if(arr[i][j]==arr[i][j+1]) {
                    set.add(new Node(i,j));
                    set.add(new Node(i,j+1));
                }
                
            }
        }       
        
        
        // 다른 원판과 인접하는것
        for(int i=1; i<n; i++) {
            for(int j=1; j<=m; j++) {
                if(arr[i][j]==0) {
                    continue;
                }
                if(arr[i][j] == arr[i+1][j]) {
                    set.add(new Node(i,j));
                    set.add(new Node(i+1,j));
                }
            }
        }
        
    }
    public static void rotate(int i) {
        int tmp;
        if(d==0) {  // 시계방향
            tmp = arr[i][m];
            for(int j=m; j>1; j--) {
                arr[i][j] = arr[i][j-1];
            }
            arr[i][1] = tmp;
            
        }
        else {
            tmp = arr[i][1];
            
            for(int j=1; j<m; j++) {
                arr[i][j] = arr[i][j+1];
            }
            arr[i][m] = tmp;
        }
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}