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

문제내용

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

17822번: 원판 돌리기

반지름이 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번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

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

 

원판을 아래와 같은 방법으로 총 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시간40분 걸려서 풀었다..

문제를 어떻게 풀어야할지 처음에 생각한 순서는 다음과같다.

 

1. x배수에 해당하는 원판을 모두 k번 돌린다.

2. 원판의 요소하나씩 체크하면서 인접한 수(상,하,좌,우)가 현재 요소값과 같다면 0으로 만들어준다.

2-1. 만약 모든 요소에서 인접한 값이 같은값이 없어서 0으로 바꾸지 못했다면 조건대로 +1,-1 해준다.

3. 1~2번은 T번만큼 반복한다.

 

간단하게는 위와같은 과정을 거치도록했다. 원판은 결국 2차원배열로 표현이 가능하다는 것만 알아두고 풀도록 하자.

그리고 주의점이 있다. 

  

예를들어 원판의 수가 다음과 같을때를 주의해야한다.

 

1 1 2 3
5 2 4 2
3 1 3 3
2 3 1 2

 위의 3번째 원판을 보면 3 1 3 3 이라는 수가 있다.(4번째 원판도 마찬가지)

이때 0번째 수인 3    ///     3번째 수인 3은 인접한 수라는걸 놓치지말자..

위의 원판을 인접한 수끼리 지워주면 다음과 같아진다.

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

 

그리고 d=1이면 반시계 방향으로 k번 돌리는 건데, 반시계 방향을 시계방향으로 바꿔서 돌릴 수 있다.

예를들어

반시계 방향으로 3번 돌림 = 시계 방향으로 m-3번 돌림

반시계 방향으로 7번 돌림 = 시계 방향으로 m-7번 돌림

반시계 방향으로 4번 돌림 = 시계 방향으로 m-4번 돌림

....

반시계 방향으로 m-1번 돌림 = 시계방향으로 m-(m-1) = 1 번 돌림.

즉, d=1이라면 k = m-k 라고 생각하고 풀면된다.(시계방향으로 바꾸는것)

 

마지막으로 평균값을 구할때 소숫점 자리도 판단해야 하기 때문에 평균값의 자료형은 double이어야 한다는걸 주의하자.

 

코드를 보자.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n,m,t;
	static int x,d,k;
	static boolean change;
	static int[][] map;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static class Node{
		int x,y,v;
		public Node(int x, int y, int v) {
			this.x = x;
			this.y = y;
			this.v = v;
		}
		
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		t = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken()); //x->몇번째 원판인지
			d = Integer.parseInt(st.nextToken()); //d->방향은 어디(0:시계, 1:반시계)
			k = Integer.parseInt(st.nextToken()); //k->원판 몇번 회전시킬껀지
			change = false;//true:인접값을 바꾼적있다. false:바꾼적 없다->평균값구하고 +1,-1해줘야함.
			
			int bea = 1;//배수
			while(true) {
				int xx = (x*bea)-1;//원판=행 -> 인덱스로 취급해야해서 -1해줌.
				if(xx>=n) break;//원판 개수보다 커지면 그만 돌리기.
				rotation(xx);//돌리기
				bea++;
			}
			
			//원판 요소 하나씩 모두 탐색
			for(int xx=0; xx<n; xx++) {
				for(int yy=0; yy<m; yy++) {
					BFS(xx,yy,map[xx][yy]);
				}
			}
			
			//평균값 구해서 +1,-1해줌.
			if(!change) avgMap();
		}//for
		
		
		int sum = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				sum+=map[i][j];
			}
		}
		System.out.println(sum);
	}
	
	//원판 돌리기 -> 요소값 이동
	public static void rotation(int x) {
		int kk = k;
		if(d==1) kk = m-k;//시계방향으로 바꾸기
		
		//원판 돌리기 -> x행에 있는 요소값들을 오른쪽으로 kk칸씩 이동.
		while(kk>0) {
			int temp = map[x][m-1];
			for(int i=m-1; i>=1; i--) 
				map[x][i] = map[x][i-1];
			map[x][0] = temp;
			kk--;
		}
	}
	
	//x행y열에 있는 값과 상하좌우에 인접한 값은 모두 0으로 바꾼다.
	public static void BFS(int x, int y, int v) {
		if(v==0) return;//만약 현재 값이 0이면 종료.
		
		Queue<Node> q = new LinkedList<>();
		boolean[][] check = new boolean[n][m];
		boolean flag = false;//인접값이 하나라도 바뀌면 true로 바뀜.
		check[x][y] = true;
		q.add(new Node(x, y, v));
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if(nx<0 || ny<0 || nx>=n || ny>=m) {
					// ny<0 이다.->현재열이 0열이다.   (x행0열) == (x행m-1열) 이면 인접한거임. 
					if(ny<0 && map[nx][m-1]==cur.v && !check[nx][m-1]) {
						q.add(new Node(nx, m-1, map[nx][m-1]));
						map[nx][m-1]=0;
						check[nx][m-1] = true;
						flag=true;
					}
					//위와 마찬가지 원리
					else if(ny>=m && map[nx][0]==cur.v && !check[nx][0]) {
						q.add(new Node(nx, 0, map[nx][0]));
						map[nx][0]=0;
						check[nx][m-1] = true;
						flag=true;
					}
					continue;
				}
				
				//인접값이 같을때
				if(map[nx][ny]==cur.v && !check[nx][ny]) {
					q.add(new Node(nx,ny,map[nx][ny]));
					map[nx][ny]=0;
					check[nx][ny]=true;
					flag=true;
				}
			}
		}
		
		if(flag) {//한번이라도 바뀌었으면
			map[x][y]=0;//가장처음에 탐색한값도 0으로 바꿔주기
			change = true;
		}
	}
	
	//평균값 구해서 +1,1해주기.
	public static void avgMap() {
		double avg=0, cnt=0, sum=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]==0)continue;
				cnt++;
				sum+=map[i][j];
			}
		}
		avg = sum/cnt;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]==0)continue;
				if(avg<map[i][j]) map[i][j]--;
				else if(avg>map[i][j]) map[i][j]++;
			}
		}
	}
}

 

---

마치며

솔직히 말해서 효율이 좋은 풀이는 아닌거 같다. 그래도 풀었다는게 중요한거고, 다른 사람들 풀이를 보면서 어떻게 효율이 좋게 풀수 있는지 보면 된다고 생각한다.