[BOJ 17822] 원판 돌리기 (Java)

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

17822번: 원판 돌리기

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

public class Main_BOJ_17822 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M, T;
	static int[][] map;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		int x, d, k;
		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+1][M+1];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=1; 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());
			d=Integer.parseInt(st.nextToken());
			k=Integer.parseInt(st.nextToken());
			rotate(x,d,k);
			if (!search()) {
				calculate();
			}
		}
		int answer=0;
		for (int i=1; i<=N; i++) {
			for (int j = 1; j <= M; j++) {
				answer+=map[i][j];
			}
		}
		System.out.println(answer);
	}
	private static void calculate() {
		int sum=0;
		int cnt=0;
		for (int i=1; i<=N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map[i][j]>0) {
					sum+=map[i][j];
					cnt++;
				}
			}
		}
		double avg=(double)sum/cnt;
		for (int i=1; i<=N; i++) {
			for (int j = 1; j <= M; j++) {
				if (map[i][j]>0) {
					if (map[i][j]>avg) map[i][j]-=1;
					else if (map[i][j]<avg) map[i][j]+=1;
				}
			}
		}
		
	}
	
	private static boolean search() {
		visited=new boolean[N+1][M+1];
		boolean flag=false;
		for (int i=1; i<=N; i++) {
			for (int j = 1; j <= M; j++) {
				if (!visited[i][j] && map[i][j]>0) {
					int val=map[i][j];
					if (dfs(i,j,val)) {
						flag=true;
					}
					else {		//인접한 거 발견 못했을 경우 다시 되돌려주기
						map[i][j]=val;
					}
				}
			}
		}
		return flag;
	}
	
	private static boolean dfs(int r, int c, int val) {
		boolean flag=false;
		visited[r][c]=true;
		map[r][c]=0;
		for (int i=0; i<4; i++) {
			int nr=r+dr[i];
			int nc=c+dc[i];
			if (nr<=0 || nr>N) continue;
			if (nc==0) nc+=M;
			else if (nc==M+1) nc-=M;
			if (!visited[nr][nc] && map[nr][nc]==val) {
				dfs(nr,nc,val);	//인접하면서 수가 같은 걸 하나라도 찾을 경우
				flag=true;
			}
		}
		return flag;
	}
	private static void rotate(int x, int d, int k) {
		for (int i=x; i<=N; i+=x) {
			int[] temp=new int[M+1];
			for (int j=1; j<=M; j++) {
				if (d==0) {
					int idx=j, cnt=0;
					while (cnt<k) {
						idx=(idx+1)%M;
						if (idx==0) idx=M;
						cnt++;
					}
					temp[idx]=map[i][j];	
				}
				else if (d==1) {
					int idx=j, cnt=0;
					while (cnt<k) {
						idx=(idx-1)%M;
						if (idx==0) idx=M;
						cnt++;
					}
					temp[idx]=map[i][j];
				}
			}
			map[i]=Arrays.copyOf(temp, M+1);
		}
	}

}

어떻게 회전 시킬까? 에 대한 부분이 까다로웠다. 인덱스를 1부터 시작해서 고민을 많이 했었는데..

다른 분들의 코드를 보니 원판의 번호를 나타내는 부분, 즉 행 부분은 1부터 시작하고(배수별로 움직이므로),

열 부분은 0부터 시작해서 애초에 혼란이 생길 수 있는 부분을 막아 주었다.

void rot(int lev, int many) {		//시계방향으로만 회전
	for (int k = 0; k < many; k++) {
		int temp = arr[lev][m - 1];
		for (int i = m-1; i > 0; i--) 
			arr[lev][i] = arr[lev][i - 1];		
		arr[lev][0] = temp;
	}
}

(출처: https://imnotabear.tistory.com/215 님)

 

-뒤에서부터 움직이면 따로 temp에 값 저장할 필요 X이다.

-반시계 방향으로 움직일 경우, k가 반시계 방향으로 움직인 경우= col-k만큼 시계방향으로 움직인 것과  일치하므로 k값만 조정해준다.