[문제] 백준 17822번 원판 돌리기

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

풀이

 

왼쪽, 오른쪽 회전만 주의하면! 되는 듯

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

public class BOJ_17822 {
	static int N,M,T;
	static int map[][];
	static boolean isAdj;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());	// 반지름: 1~N
		M = Integer.parseInt(st.nextToken());	// 원 하나당 수의 개수: M 
		T = Integer.parseInt(st.nextToken());	// 회전 회수
	
		map = new int[N+1][M];	//원판 번호 1번부터 N번
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}// init map
		
		for(int i=0;i<T;i++) {
			st = new StringTokenizer(in.readLine()," ");
			int x = Integer.parseInt(st.nextToken());	// 원 번호 : x 배수
			int d = Integer.parseInt(st.nextToken());	// 0: 시계, 1: 반시계 
			int k = Integer.parseInt(st.nextToken());	// k칸 회전
			for(int j=x;j<=N;j+=x) {
				for(int a=0;a<k;a++) {
					rotate(j,d);	// 원판 번호, d 방향
				}
			}
			isAdj = false;
			process();	// 인접하면서 같은 수인거 지우기(0으로 표시)
		} // instruction
		
		int sum = 0;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]>0) sum += map[i][j];
			}
		}
		System.out.println(sum);
	}
	
	private static void process() {
		if(!isLeft()) return;	// 남아있는 수 없으면 리턴
		
		boolean[][] visited =new boolean[N+1][M];
		
		int sum = 0, total = 0;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<M;j++) {
				if(!visited[i][j] && map[i][j]>0)
					isAdjacent(i, j, visited);
				
				if(map[i][j]>0) {
					sum += map[i][j];
					total++;
				}
			}
		}
		// 인접하면서 같은 수 있다면
		if(isAdj) {
			// 지우기
			for(int i=1;i<=N;i++) {
				for(int j=0;j<M;j++) {
					if(visited[i][j]) {
						map[i][j] = 0;
					}
				}
			}
		}
		// 인접 & 같은 수 없으면
		if(!isAdj) {
//			int avg = sum/total;
			int avg = sum;
			for(int i=1;i<=N;i++) {
				for(int j=0;j<M;j++) {
					if(map[i][j]==0) continue;
					if(map[i][j]*total>avg) {
						map[i][j]--;
					}else if(map[i][j]*total<avg) {
						map[i][j]++;
					}
				}
			}
		}
			
	}
	static void isAdjacent(int num, int idx, boolean[][] visited) {
		int left = (idx+M-1) % M;	// 같은 판 왼쪽 수
		int right = (idx+1) % M;	// 같은 판 오른쪽 수
		int down = num-1;			// 아래 판
		int up = num+1;				// 위 판
		int standard = map[num][idx];	// 현재 번호(기준점)
		
		if(standard == map[num][left] && !visited[num][left]) {
			isAdj =true;
			visited[num][left] = true;
			isAdjacent(num, left, visited);
		}
		if(standard == map[num][right] && !visited[num][right]) {
			isAdj =true;
			visited[num][right] = true;
			isAdjacent(num, right, visited);
		}
		if(down>=1 && down<=N && standard == map[down][idx]&& !visited[down][idx]) {
			isAdj =true;
			visited[down][idx] = true;
			isAdjacent(down, idx, visited);
		}
		if(up>=1 && up<=N && standard == map[up][idx] && !visited[up][idx]) {
			isAdj =true;
			visited[up][idx] = true;
			isAdjacent(up, idx, visited);
		}
		
	}
	static boolean isLeft() {
		for(int i=1;i<=N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]>0) return true;
			}
		}
		return false;
	}
	private static void rotate(int num, int d) {
		if(d==0) {	// 시계 방향
			int tmp = map[num][M-1];
			for(int i=M-1;i>0;i--) {
				map[num][i] = map[num][i-1];
			}
			map[num][0] = tmp;
		}
		else if(d==1) {// 반시계 방향
			int tmp = map[num][0];
			for(int i=0;i<M-1;i++) {
				map[num][i] = map[num][i+1];
			}
			map[num][M-1] = tmp;
		}
	}
}