[백준] 17822 원판 돌리기

알고리즘 공부/구현 , 시뮬레이션

[백준] 17822 원판 돌리기

kdhoooon 2021. 10. 15. 15:37

문제

반지름이 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이다.

번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

풀이

우선 과녁판은 2차원 배열로 구성하였다.

회전하는 방식은

시계 방향 : m-1 번째 인덱스의 값이 0번째로 오고 나머지는 하나씩 밀려야한다.

시계 방향 순서

1. m - 1 번째 인덱스 값 미리 저장

2. for( i = m - 1 -> 1 ) { board[xi][i] = board[xi][i - 1] }

3. board[xi][0] = 1번에서 저장한 값

반시계 방향 : 0 번째 인덱스의 값이 m - 1 번째로 가고 나머지는 하나씩 당겨야한다.

반시계 방향 순서

1. 0 번째 인덱스 값 미리 저장

2. for( i = 1 -> m - 1 ) { board[xi][i] = board[xi][i - 1] }

3. board[xi][m - 1] = 1번에서 저장한 값

위와 같은 방식으로 구현하면 된다.

<회전 코드>

public static void turnBoard(int x, int d, int k) {
	
	for(int xi = x - 1 ; xi < n ; xi += x) {
		// 반시계 방향
		if(d == 1) {
			for(int times = 0 ; times < k ; times++) {
				int tmp = board[xi][0];
				
				for(int i = 0 ; i < m - 1 ; i++) {
					board[xi][i] = board[xi][i + 1];
				}
				
				board[xi][m - 1] = tmp;
			}
		}
		else {
			for(int times = 0 ; times < k ; times++) {
				int tmp = board[xi][m - 1];
				
				for(int i = m - 1 ; i > 0 ; i--) {
					board[xi][i] = board[xi][i - 1];
				}
				
				board[xi][0] = tmp;
			}
		}
	}		
	
	return;
}

이제 나머지는 인접한 곳에 같은 수가 있는 지를 확인하면 된다.

확인 하는 코드는 BFS 를 이용 하였다.

일반적으로 map 을 훑는 방식하고 비슷한데 원이기 때문에 j 의 값은 양끝이 존재하지 않는다.

따라서 j = (j + m) % m 을 해주어 인덱스를 조정해 주었다.

<BFS 코드>

public static boolean bfs(int i, int j) {
	
	visited[i][j] = true;
	Queue<Node> queue = new LinkedList<>();
	queue.add(new Node(i, j));
	
	int score = board[i][j];
	boolean isErased = false;
	while(!queue.isEmpty()) {
		Node top = queue.poll();
		
		for(int d = 0 ; d < 4 ; d++) {
			int ni = top.i + move[d][0];
			int nj = top.j + move[d][1];
			
			nj = (nj + m) % m;
			if(ni < 0 || ni >= n || board[ni][nj] == 0 || board[ni][nj] != score || visited[ni][nj]) { continue; }
			
			visited[ni][nj] = true;
			board[ni][nj] = 0;
			isErased = true;
			
			queue.add(new Node(ni, nj));
		}
	}
	
	if(isErased) {
		board[i][j] = 0;
	}
	return isErased;
}

public static void eraseBoard() {
	
	boolean isErased = false;	
	
	visited = new boolean[n][m];
	
	for(int i = 0 ; i < n ; i++) {
		for(int j = 0 ; j < m ; j++) {
			if(visited[i][j] || board[i][j] == 0 ) {continue;}
			
			if(!isErased) {
				isErased = bfs(i, j);
			}
			else {
				bfs(i, j);
			}
		}
	}
	
	if(!isErased) {
		int[] res = sumBoard();
		
		double avg = (double)res[0] / res[1];
		changeScore(avg);		
	}
	
	return;
}

위와 같이 확인을 한 뒤에 하나라도 지워진 것이 있다면 isErased 를 바꿔준다.

하나도 지워진게 없다면 평균값을 구해 더해주고 빼주면 된다.( 단, 평균과 같으면 아무 작업도 하면 안된다. 예제 5번이 그 반례다)

<전체코드>

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 int[][] board;
	static boolean[][] visited;
	static int n, m, t;
	static int[][] move = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		n = parseInt(st.nextToken());
		m = parseInt(st.nextToken());
		t = parseInt(st.nextToken());
		
		board = new int[n][m];
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			for(int j = 0 ; j < m ; j++) {
				board[i][j] = parseInt(st.nextToken());
			}
		}
		
		for(int i = 0 ; i < t ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int x = parseInt(st.nextToken());
			int d = parseInt(st.nextToken());
			int k = parseInt(st.nextToken());
			
			turnBoard(x, d, k);
			eraseBoard();
		}
		
		System.out.println(sumBoard()[0]);
	}
	
	public static void changeScore(double avg) {
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < m ; j++) {
				if(board[i][j] == 0) { continue; }
				
				if(avg < (double)board[i][j]) {
					board[i][j]--;
				}
				else if(avg > (double)board[i][j]) {
					board[i][j]++;
				}
			}
		}
	}
	
	public static boolean bfs(int i, int j) {
		
		visited[i][j] = true;
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(i, j));
		
		int score = board[i][j];
		boolean isErased = false;
		while(!queue.isEmpty()) {
			Node top = queue.poll();
			
			for(int d = 0 ; d < 4 ; d++) {
				int ni = top.i + move[d][0];
				int nj = top.j + move[d][1];
				
				nj = (nj + m) % m;
				if(ni < 0 || ni >= n || board[ni][nj] == 0 || board[ni][nj] != score || visited[ni][nj]) { continue; }
				
				visited[ni][nj] = true;
				board[ni][nj] = 0;
				isErased = true;
				
				queue.add(new Node(ni, nj));
			}
		}
		
		if(isErased) {
			board[i][j] = 0;
		}
		return isErased;
	}
	
	public static void eraseBoard() {
		
		boolean isErased = false;	
		
		visited = new boolean[n][m];
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < m ; j++) {
				if(visited[i][j] || board[i][j] == 0 ) {continue;}
				
				if(!isErased) {
					isErased = bfs(i, j);
				}
				else {
					bfs(i, j);
				}
			}
		}
		
		if(!isErased) {
			int[] res = sumBoard();
			
			double avg = (double)res[0] / res[1];
			changeScore(avg);		
		}
		
		return;
	}

	public static void turnBoard(int x, int d, int k) {
		
		for(int xi = x - 1 ; xi < n ; xi += x) {
			// 반시계 방향
			if(d == 1) {
				for(int times = 0 ; times < k ; times++) {
					int tmp = board[xi][0];
					
					for(int i = 0 ; i < m - 1 ; i++) {
						board[xi][i] = board[xi][i + 1];
					}
					
					board[xi][m - 1] = tmp;
				}
			}
			else {
				for(int times = 0 ; times < k ; times++) {
					int tmp = board[xi][m - 1];
					
					for(int i = m - 1 ; i > 0 ; i--) {
						board[xi][i] = board[xi][i - 1];
					}
					
					board[xi][0] = tmp;
				}
			}
		}		
		
		return;
	}
	
	public static int[] sumBoard() {
		
		int[] result = new int[2];
		for(int i = 0 ; i < n ; i++) {
			for(int j  = 0 ; j < m ; j++) {
				if(board[i][j] != 0) {
					result[1]++;
				}
				result[0] += board[i][j];
			}
		}
		
		return result;
	}
	
	
	static class Node{
		int i, j;
		
		Node(int i, int j){
			this.i = i;
			this.j = j;
		}
	}
}

'알고리즘 공부 > 구현 , 시뮬레이션' 카테고리의 다른 글

[백준] 16236 아기상어 (0)	2021.10.16
[백준] 20057 마법사 상어와 토네이도 (0)	2021.10.16
[백준] 17825 주사위 윷놀이 (0)	2021.10.15
[백준] 17143 낚시왕 (0)	2021.10.14
[백준] 1922 쿼드트리 (0)	2021.08.22

현재글[백준] 17822 원판 돌리기

다이나믹프로그래밍, dp, 분류, 이분탐색, 완전탐색, BFS, string, 알고리즘, 최단거리, 구현, 그래프탐색, 그리디알고리즘, 백준, dfs, 시뮬레이션, 자료구조, 그래프, 우선순위큐, 깊이우선탐색, 프로그래머스,

Today :
Yesterday :

개발자꿀꿀이