[백준] 17822. 원판 돌리기

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

17822번: 원판 돌리기

---

2019 하반기 삼성 공채 SW 역량테스트 시뮬레이션 문제 입니다. 제가 봤던 시간대가 아닌 다른 시간대에 문제였는데 정답률을 보니까 더 어려웠던 것 같습니다. 원판을 차례대로 2차원 배열에 저장했는데, 제가 이 문제를 풀면서 실수 했던 점은 다음과 같습니다.

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

위 처럼 저장되어 있는 3개의 원판에 지워져야 할 수는 빨간색으로 표시되어 있는 3개의 2 입니다. 하지만 저는 배열의 (0, 0) 부터 끝까지 행별로 확인하면서 접한 수 들을 차례대로 지웠기 때문에 다음과 같이 파란색으로 표시된 곳만 지워지게 됩니다.

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

그래서 해결 방법은 각 자리의 숫자들의 위치와 값을 객체화 했습니다. 그리고 일단 지워진 수가 아니라면 모두 Queue 자료구조에 담고 BFS 로 4방향을 탐색하면서 같은수라면 지우는 방법을 통해 이미 지워진 수라도 다음에 확인했을 때 영향이 없도록 했습니다.

[ 문제 풀이 ]

1. 2차원 int 배열 circulars에 원판에 적힌 번호들을 저장합니다.

2. Pair Class 에는 원판에 적힌 위치 (r, c) 와 값(v) 를 저장합니다.

3. T번 회전하기 때문에 한번의 T를 받을 때 마다 rotating() 함수로 회전을 시켜줍니다.

4. rotating() 함수에서 시계방향이라면 rightRotate(), 반시계방향이라면 leftRotate()로 선형 배열을 회전시켜줍니다.

5. 그리고 remove() 함수를 통해서 인접한 수를 삭제합니다.

        5-1. 지워지지 않은 수라면(0이 아니라면) queue에 넣습니다.

        5-2. queue의 앞에서부터 4방향을 탐색하며 자기 자신과 같은지 판단합니다.

        5-3. 여기에서 문제는 원판이고, 저는 선형 자료구조로 저장했기 때문에 두가지를 판단해야 합니다.

              첫 번째는 다음 좌표들이 배열 범위 안이라면 바로 데이터를 지우면 되지만

              두 번째는 배열 밖을 벗어나면 오른쪽으로 벗어났는지 왼쪽으로 벗어났는지 판단하여 인덱스를 처음이나

                           끝으로 바꾼 좌표의 값을 봐야합니다.

6. 인접한 수를 더이상 지울게 없다면 평균을 구하고 평균보다 큰 수는 1을 더해주고 작은수는 1을 빼줍니다.

---

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 class Pair {
		int r;
		int c;
		int v;
		
		Pair(int r, int c, int v){
			this.r=r;
			this.c=c;
			this.v=v;
		}
	}
	
	static int N, M, T, x, d, k;
	static int[][] circulars, dir = {{0,1},{0,-1},{-1,0},{1,0}};
			
	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());	// 회전수
		circulars = new int[N+1][M];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				circulars[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());
			rotating(x, d, k);
		}
		
		int answer = 0;
		
		for(int i=1; i<=N; i++) {
			for(int j=0; j<M; j++) {
				if(circulars[i][j] != 0) {
					answer += circulars[i][j];
				}
			}
		}
		
		System.out.println(answer);
	}

	public static void rotating(int x, int d, int k) {
		// d=0 시계방향, 1, 반시계방향
		for(int i=x; i<=N; i+=x) {
			if(d==0) {
				for(int j=0; j<k; j++) rightRotate(i);
			} else if(d==1) {
				for(int j=0; j<k; j++) leftRotate(i);
			}
		}
		
		if(!remove()) {
			int cnt = 0;
			double sum = 0;
			for(int i=1; i<=N; i++) {
				for(int j=0; j<M; j++) {
					if(circulars[i][j] != 0) {
						cnt++;
						sum += circulars[i][j];
					}
				}
			}
			
			double avg = sum/cnt;
			
			for(int i=1; i<=N; i++) {
				for(int j=0; j<M; j++) {
					if(circulars[i][j] != 0) {				
						if(circulars[i][j] > avg) circulars[i][j]--;
						else if(circulars[i][j] < avg) circulars[i][j]++;
					}
				}
			}
		}
	}

	public static boolean remove() {
		Queue<Pair> queue = new LinkedList();
		 
		for(int i=1; i<=N; i++) {
			for(int j=0; j<M; j++) {
				if(circulars[i][j] != 0) {
					queue.offer(new Pair(i, j, circulars[i][j]));
				}
			}
		}
		
		// 한번이라도 숫자가 지워졌는지 안지워졌는지 확인하는 변수
		boolean flag = false;
	
		while(!queue.isEmpty()) {
			
			// 네 방향에 같은 숫자가 하나라도 있는지 체크하는 변수
			boolean check = false;
			
			Pair p = queue.poll();
			
			for(int k=0; k<4; k++) { // 오 왼 위 아래
				int nx = p.r + dir[k][0];
				int ny = p.c + dir[k][1];
				
				if(isInside(nx, ny)) {
					if(circulars[nx][ny] == 0) continue;
					if(circulars[nx][ny] == p.v) {
						circulars[nx][ny] = 0;
						check = true;
					}
				} else {
					switch(k) {							
					case 0: // 오
						if(circulars[nx][0] == p.v) {
							circulars[nx][0]=0;
							check = true;
						}
						break;
					case 1: // 왼
						if(circulars[nx][M-1] == p.v) {
							circulars[nx][M-1]=0;
							check = true;
						}
						break;
					}
				}
			}
			if(check) {
				circulars[p.r][p.c] = 0;
				flag = true;
			}
		}
		return flag;
	}

	public static void leftRotate(int r) {
		int temp = circulars[r][0];
		for(int i=0; i<M-1; i++) 
			circulars[r][i] = circulars[r][i+1];
		circulars[r][M-1] = temp;
	}

	public static void rightRotate(int r) {
		int temp = circulars[r][M-1];
		for(int i=M-1; i>0; i--) 
			circulars[r][i] = circulars[r][i-1];
		circulars[r][0] = temp;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=1 && x<=N && y>=0 && y<M;
	}

}