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

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

 

 

[ 문제 요약 ]

• 반지름이 1,2,3... N인 원판이 크기가 작아지는 순으로 바닥에 놓여있습니다. 원판의 중심은 모두 같고 1번 원판이 가장 작은 원판입니다.
• 각 원판에는 m 개의 정수가 적혀있습니다.
• 원판 회전은 독립적으로 이루어집니다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않습니다.
• 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 합니다.
• 원판을 아래와 같은 방법으로 총 T 번 회전시키려고 합니다. 원판의 회전 방법은 미리 정해져 있고, i 번째 회전할 때 사용하는 변수는 xi, di, ki입니다.
• 번호가 xi의 배수인 원판을 di 방향으로 ki 칸 회전시킵니다. ( di의 값 0은 시계, 1은 반시계 )
• 원판 전체에 0이 아닌 값이 하나라도 있다면, 인접하면서 수가 같은 것을 모두 찾습니다.
• 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 0으로 만듭니다.
• 없는 경우에는 전체 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더합니다.
• 원판을 T 번 회전시킨 후 원판에 적힌 수의 합을 출력합니다.

 

[ 테스트 케이스 설명 ]

4 4 1// 원판의 수(2<=50), 원판에 적힌 숫자 개수(2<=50), 회전횟수(1<=50)
1 1 2 3 // 원판 수만큼 적힌 수가 주어짐(1<=1000)
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1 // 회전 횟수만큼 주어지며 xi, di, ki가 주어짐
답 : 30

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

문제 지문은 헷갈리게 적은 것이 많습니다.

 

원판을 돌릴 때는 전체 원판을 돌립니다. 원판 평균 확인 시 전체 원판에 대해 확인합니다.

 

그리고 같은 숫자를 제거할 때, 원판 안의 숫자는 원형으로 이어지고, 원판 끼리는 이어지지 않아 dfs 탐색 시 신경 써주어야 합니다.

평균을 구할 때는 실수를 사용해야 합니다. 정수를 쓴다면 아래와 같은 오류가 생깁니다.

 

평균이 3.5일 때, 숫자 3은 3.5보다 작아 +1을 해주어야 하지만, 정수로 연산시 평균이 3이 되어 숫자 3에 대해 +1을 해줄 수 없게 됩니다.

 

원판을 돌릴 때는 모듈러 연산과 offset으로 왼쪽, 오른쪽 상관없이 하나의 함수로 원판을 돌릴 수 있습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{1,0},{0,1},{-1,0},{0,-1}};
	static boolean visit[][];
	static boolean find;
	static int map[][];
	static int N, M, T;
	static int x, d, k;
	static int offset;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 원판의 수(2<=50)
		M = Integer.parseInt(st.nextToken());// 원판에 적힌 숫자 개수(2<=50)
		T = Integer.parseInt(st.nextToken());// 회전횟수(1<=50)
		map = new int[N][M];
		visit = new boolean[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());
		}
		
		while(T-->0)
		{
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken()); // 배수
			d = Integer.parseInt(st.nextToken()); // 방향 0은 시계, 1은 반시계
			k = Integer.parseInt(st.nextToken()) % M; // 회전 칸수
			offset = 0;
			if(d == 1){
				k = -k;// 반시계면 k는 음수
				offset = M;// 반시계면 offset은 M
			}
			
			clear();
			rotate();
			if(!deleteSame())
				calAverage();
		}
		
		int sum = 0;
		
		for(int i=0; i<N; i++)
			for(int j=0; j<M; j++)
				sum += map[i][j];
		
		System.out.print(sum);
	}
	static void clear() {
		for(int i=0; i<N; i++)
			for(int j=0; j<M; j++)
				visit[i][j] = false;
	}
	static void rotate() {
		for(int i=x; i<=N; i+=x)
		{
			int newArr[] = new int[M];
			
			for(int j=0; j<M; j++)
				newArr[(j + k + offset) % M] = map[i - 1][j];
			
			map[i - 1] = newArr;
		}
	}
	static boolean deleteSame() {
		find = false;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0 || visit[i][j])
					continue;
				
				visit[i][j] = true;
				
				if(dfs(i, j, map[i][j], true))
					find = true;
			}
		}
		
		return find;
	}
	static boolean dfs(int i, int j, int target, boolean isFirst) {
		boolean same = !isFirst && map[i][j] == target;
		
		for(int xy[] : dxy)
		{
			int ni = i + xy[0];
			int nj = (j + xy[1] + M) % M;
			
			if(ni < 0 || N <= ni || visit[ni][nj] || map[ni][nj] != target)
				continue;
			
			visit[ni][nj] = true;
			same = true;
			
			dfs(ni, nj, target, false);
		}
		
		if(same)
			map[i][j] = 0;
		
		return same;
	}

	static void calAverage() {
		int sum = 0;
		int cnt = 0;
		
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<M; j++)
			{
				if(map[i][j] == 0)
					continue;
				
				sum += map[i][j];
				cnt += 1;
			}
		}
		
		if(cnt == 0)return;
		
		double avg = (double)sum / cnt;
		
		for(int i=0; i<N; i++)
			for(int j=0; j<M; j++)
				if(map[i][j] == 0) continue;
				else if(map[i][j] > avg)map[i][j]--;
				else if(map[i][j] < avg)map[i][j]++;
	}
}