[BOJ/17822] - 원판돌리기

문제

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

17822번: 원판 돌리기

 

---

코드

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

public class Main {
	static int N, M, T;
	static int[][] arr;
	static int x, d, k;
	static int sum, cnt;
	static boolean flag;

	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()); // 명령어 갯수
		arr = new int[N][M]; // 원판
		sum = 0;// 초기화
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				sum += arr[i][j];
				cnt++;
			}
			// System.out.println(Arrays.toString(arr[i]));
		}

		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();
		}

		System.out.println(sum);
	}

	static void rotate() {
		// 먼저 회전 시키기
		for (int i = x; i <= N; i += x) { // 실제 배열은 0,0 부터 시작함 고로 밑에 i-1 처리해줌
			int[] tmp = new int[M]; // 임시 배열
			if (d == 0) {// 시계방향
				for (int j = 0; j < M; j++) {
					// tmp[0]=arr[0-k]
					tmp[j] = arr[i - 1][(j - k + M) % M];
				}
			} else { // 반시계방향
				for (int j = 0; j < M; j++) {
					// tmp[0]=arr[0+k]
					tmp[j] = arr[i - 1][(j + k + M) % M];
				}
			}
			arr[i - 1] = tmp;
		}

		flag = false;// 인접한 수가 있는 지 체크용 플래그
		// 탐색 돌려서 인접한 수 찾기
		boolean[][] visit = new boolean[N][M];
		boolean[][] find = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// 시작점
				if (visit[i][j] || arr[i][j] == 0 || find[i][j]) { // 방문했거나 숫자가 0이면 넘기기
					continue;
				}
				bfs(i, j, visit, find);
			}
		}
		if (flag) {
			// System.out.println("인접한 같은 수가 있는 경우");
			for (int i = 0; i < N; i++) {
				// System.out.println(Arrays.toString(find[i]));
				for (int j = 0; j < M; j++) {
					if (find[i][j]) {
						sum -= arr[i][j];
						arr[i][j] = 0;
						cnt--;
					}
				}
			}
		} else {
			// 다 돌았는데 false면 평균 기준으로 + - 하기 평균은 소수점까지 고려하기
			double avg = (double) sum / cnt;
			// System.out.println("평균 " + avg);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (arr[i][j] == 0) {
						continue;
					} else if (arr[i][j] > avg) {
						arr[i][j] -= 1;
						sum -= 1;
					} else if (arr[i][j] < avg) {
						arr[i][j] += 1;
						sum += 1;
					}
				}
			}
		}
		// System.out.println("명령어 끝나기 전에 상황 " + sum + " " + cnt);
	}

	static int[] dx = { 0, 0, 1, -1 };\
	static int[] dy = { 1, -1, 0, 0 };

	static void bfs(int x, int y, boolean[][] visit, boolean[][] find) {
		// 탐색해서 인접한 수 찾기
		// System.out.println("bfs 시작 " + x + " " + y + " " + arr[x][y]);
		visit[x][y] = true;
		Queue<int[]> q = new LinkedList<>(); // 행, 열, 숫자 저장하기
		q.add(new int[] { x, y, arr[x][y] });

		while (!q.isEmpty()) {
			int[] tmp = q.poll();
			for (int i = 0; i < 4; i++) {
				int cx = tmp[0] + dx[i]; // 원판
				int cy = (tmp[1] + dy[i] + M) % M; // 원판 내부

				if (cx >= N || cx < 0 || visit[cx][cy] || tmp[2] != arr[cx][cy]) {
					// 범위를 넘어갔거나 방문했거나 숫자가 다르면 넘어가기
					continue;
				}

				flag = true;
				visit[cx][cy] = true;
				find[x][y] = true;
				// find[tmp[0]][tmp[1]] = true;
				find[cx][cy] = true;
				q.add(new int[] { cx, cy, arr[cx][cy] });

			}
		}
	}
}

 

 

---

해설

사용한 알고리즘, 유형

명령어대로 돌리고
bfs로 탐색하여 인접한 수들을 체크
같은 수가 있으면 제거
없으면 평균기준으로 + - 처리

---

이슈

문제 자체는 하라는 대로 하면되는데

그만큼 조건이 많아서 문제를 잘 읽으면서 풀어야했다.

 

사소한 실수가 많아서 많이 틀렸다.....

정신차리고 문제 풀자!

민망하지만

n의 배수를 처리할때

for(int i=0;i<N;i++){
 if(i%n==0){

   continue; 는 더러워서

수정한다는게

for(int i=0;i<N;i+=n){

 으로 수정해서 틀렸음....

for(int i=n;i<N;i+=n){

으로 했어야 했는데...