백준 17822 : 원판 돌리기

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

17822번: 원판 돌리기

[ 문제풀이 ]

이번에도 동일하게 시뮬레이션 문제이다. 주어진 조건대로 구현하면 정답을 쉽게 맞힐 수 있을 것이다.

조건을 하드 코딩해서 풀어도 되지만 하드 코딩하면 실수 시 디버깅하기가 힘들기 때문에 조금 구현하기 쉽게 설계하여 풀었다.

​1. 먼저 방향을 한 방향으로 통일한다. 반시계 방향을 시계 방향으로 변경 후 한 방향으로 회전시키는 함수만 구현하면 훨씬 간단하다.

​2. 인접한 원판들을 해결해야 하는데 단순히 1, N 원판 / 나머지 원판으로 확인하는 함수를 구현해도 되지만 나는 간단하게 2차원 visit 배열을 이용해서 dfs를 돌렸다. dfs를 돌릴 시 조심해야 할 점은 보통 dfs는 처음에 진입하면 방문했다고 표시해 주는데 우리는 1개 이상 인접했을 때 방문 표시를 하도록 한다.

​3. 마지막으로 문제에서 조심해야 할 부분이다. 첫 번째는 원판에 적힌 수의 평균을 구할 경우 int가 아닌 double형으로 구해야 한다. 소수점을 날리면 올바른 값을 얻지 못한다. 두 번째는 당연한 소리지만 평균과 같은 수는 갱신하면 안 된다. 이를 놓치고 같은 경우에도 처리를 한다면 오답을 받을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M, T;
	static boolean find;
	static int[][] map;
	static boolean[][] visit;
	static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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];
		visit = new boolean[N+1][M];
		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			//반시계 방향인 경우 시계 방향으로 바꿔줌
			if (d == 1) k = M - k;
			
            //x의 배수인 원판을 회전
			for (int i = x; i <= N; i += x) {
				rotateTheMap(i, k);
			}
			
			//모든 원판을 돌면서 인접한 원판이 존재하는지 확인
			for (int i = 1; i <= N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (visit[i][j] || map[i][j] == 0) continue;
					dfs(i, j, map[i][j]);
				}
			}
			
			if (!find) changeTheMap();
			find = false;
			for (int i = 0; i <= N; ++i) Arrays.fill(visit[i], false);
		}
		
		bw.write(getAnswer() + "\n");
		bw.flush();bw.close();br.close();
	}
	
	public static void rotateTheMap(int x, int k) {
		int[] temp = new int[M];
		for (int i = 0; i < M; ++i) temp[(i + k) % M] = map[x][i];
		for (int i = 0; i < M; ++i) map[x][i] = temp[i];
	}
	
	public static void dfs(int y, int x, int key) {
		boolean mark = false;
	
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = (M + x + dir[d][1]) % M;
		
			if (ny < 1 || ny > N) continue;
			if (visit[ny][nx] || map[ny][nx] != key) continue;
			
			visit[ny][nx] = true;
			map[ny][nx] = 0;
			mark = true;
			dfs(ny, nx, key);
		}
		
		//처음 진입한 원판과 인접한 원판이 1개 이상이면 제거해줌
		if (mark) {
			find = true;
			map[y][x] = 0;
			visit[y][x] = true;
		}
	}
	
	public static void changeTheMap() {
		double sum = 0, cnt = 0;
		
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (map[i][j] != 0) {
					sum += map[i][j];
					cnt++;
				}
			}
		}
		
		sum /= cnt;
		
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (map[i][j] != 0) {
					if (map[i][j] > sum) {
						map[i][j]--;
					} else if (map[i][j] < sum) {
						map[i][j]++;
					}
				}
			}
		}
	}
	
	public static int getAnswer() {
		int cnt = 0;
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j < M; ++j) {
				cnt += map[i][j];
			}
		}
		return cnt;
	}
}