[백준] 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번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

 

해결방법 > 

시뮬레이션 문제로 원판이 돌아갈 때마다 인접한 노드가 같은 값을 가지는지 체크하고 삭제해준다.

 

두 가지 과정이 필요하다.

 

1) 원판돌리기

   양방향으로 데이터 입출력이 가능한 덱(Deque)를 사용해서 구현한다. 

   시계 방향이라면 끝에 있는 원소를 뽑아 첫번째 원소에 넣는다.

   반시계 방향이라면 첫번째 원소를 뽑아 끝에 넣는다.

 

2) 인접한 노드가 같은 값을 가지는지 확인

   모든 원판을 2차원 배열로 생각하고 DFS(깊이우선탐색)을 사용해 인접한 노드가 같은 값을 가지는 모든 노드를 찾는다.

   단, 원판이므로 열을 탐색할 때, 열 끝에 도달했다면 반대열부터 계속해서 탐색해준다.

 

   2-1) 탐색한 모든 경로의 길이가 1일 때 즉, 인접한 수들 중 같은 수가 없다면 모든 노드의 평균값에서 각 노드의 값이 작다면 +1 크다면 -1

   2-2) 탐색한 경로 중 길이가 2이상이 있을 경우, 경로의 모든 노드들을 삭제해준다.(-1을 저장한다)

 

[JAVA]

package baekjoon;

import java.io.*;
import java.util.*;

public class BOJ_17822 {
	static int n;
	static int m;
	static int[][] circle;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static ArrayList <Node> rlist = new ArrayList<>();
	static int[][] visit;
	static int depth = 0;
	
	public static class Node{
		int x;
		int y;
		
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	public static void turn(int[] line, int d, int k) {
		Deque <Integer> q = new LinkedList<>();
		
		for(int i = 0; i < line.length; i++) {
			q.addLast(line[i]);
		}
		
		if(d == 0) {
			for(int i = 0; i < k; i++) {
				int tmp = q.pollLast();
				q.addFirst(tmp);
			}
		}
		
		if(d == 1) {
			for(int i = 0; i < k; i++) {
				int tmp = q.pollFirst();
				q.addLast(tmp);
			}
		}
		int i = 0;
		while(!q.isEmpty()) {
			line[i] = q.poll();
			i++;
		}
	}
	
	public static void dfs(int x, int y, int v) {
		depth++;
		visit[x][y] = 1;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(ny < 0) ny = m-1;
			if(ny >= m) ny = 0;
			if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
				if(visit[nx][ny] == 0 && circle[nx][ny] == v)
					dfs(nx, ny, v);
			}
		}
	}
	
	public static void remove() {
		visit = new int[n][m];
		double sum = 0;
		int flag = 0;
		int zero = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(visit[i][j] == 0 && circle[i][j] != -1) {
					depth = 0;
					dfs(i, j, circle[i][j]);
					if(depth == 1) {
						visit[i][j] = 0;
						sum += circle[i][j];
						zero++;
					}else {
						flag = 1;
					}
				}
			}
		}
		
		if(flag == 1) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(visit[i][j] == 1)
						circle[i][j] = -1;
				}
			}
		}
		
		if(flag == 0) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(circle[i][j] > sum / zero)
						circle[i][j]--;
					else if (circle[i][j] != -1 && circle[i][j] < sum / zero)
						circle[i][j]++;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(tk.nextToken());
		m = Integer.parseInt(tk.nextToken());
		int t = Integer.parseInt(tk.nextToken());
		circle = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			tk = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				circle[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		
		for(int i = 0; i < t; i++) {
			tk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(tk.nextToken());
			int d = Integer.parseInt(tk.nextToken());
			int k = Integer.parseInt(tk.nextToken());
			int j = 1;
			while(true) {
				if(x * j-1 >= n) break;
				turn(circle[x * j - 1], d, k);
				j++;
			}
			remove();
		}
		
		int result = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(circle[i][j] != -1) {
					result += circle[i][j];
				}
			}
		}
		
		System.out.println(result);
	}
}