[BOJ] 17822. 원판돌리기 - Simulation(BFS)

[BOJ] 17822. 원판돌리기 - Simulation(BFS)

제출일 : 2019-11-11

문제 풀이 시간 : 1H 30M

난이도 : ★★★☆

Problem

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

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 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번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키지 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

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

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

Input

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

Output

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

Constraints

• 2 ≤ N, M, T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

Example

input

4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1

output

30

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

시뮬레이션으로 문제에 주어진데로 풀면 되지만 조건이 까다롭고 어려웠던 문제.

Code

언어 : JAVA

메모리 : 30,488 kb

실행시간 : 280 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, T;
    static int[][] map;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt() + 1; // 원판의 개수
        M = sc.nextInt(); // 각 원판의 정수의 개수
        T = sc.nextInt(); // 테스트 케이스 개수

        map = new int[N][M];

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        // 입력끝
        for (int i = 0; i < T; i++) {
            int x = sc.nextInt(); // 번호가 x의 배수인 원판을
            int d = sc.nextInt(); // d방향으로 (0:시계방향, 1:반시계방향)
            int k = sc.nextInt(); // k칸 회전시킨다.
            rotate(x, d, k);
            if (!check())
                edit();
        }
        System.out.println(sum());

        sc.close();
    }

    private static void edit() {
        int sum = 0, cnt = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    cnt++;
                    sum += map[i][j];
                }
            }
        }
        if (cnt == 0)
            return;
        double avg = sum / (double) cnt;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    if (map[i][j] > avg) // 평균보다 큰수
                        map[i][j]--; // 1을 빼고
                    else if (map[i][j] < avg)
                        map[i][j]++; // 1을 더한다
                }
            }
        }
    }

    private static boolean check() {
        boolean flag = false;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    if (bfs(i, j, map[i][j])) {
                        map[i][j] = 0;
                        flag = true;
                    }
                }
            }
        }
        return flag;
    }

    private static boolean bfs(int i, int j, int k) {
        Queue<int[]> q = new LinkedList<>();
        boolean flag = false;
        q.offer(new int[] { i, j });

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int r = cur[0] + dr[dir];
                int c = cur[1] + dc[dir];
                if (c == -1)
                    c = M - 1;
                else if (c == M)
                    c = 0;
                if (isRange(r, c)) {
                    if (map[r][c] == k) {
                        q.offer(new int[] { r, c });
                        map[r][c] = 0;
                        flag = true;
                    }
                }
            }
        }
        return flag;
    }

    private static boolean isRange(int r, int c) {
        if (1 <= r && r < N)
            return true;
        return false;
    }

    private static int sum() {
        int sum = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sum += map[i][j];
            }
        }
        return sum;
    }

    private static void rotate(int x, int d, int k) {
        for (int num = x; num < N; num += x) {
            int cnt = k;
            while (cnt-- != 0) { // k칸 회전
                int[] tmp = map[num].clone();// 맵 복사
                switch (d) {
                case 0: // 시계방향 회전(오른쪽으로)
                    for (int j = 0; j < M - 1; j++) {
                        map[num][j + 1] = tmp[j];
                    }
                    map[num][0] = tmp[M - 1];
                    break;
                case 1: // 반시계방향 회전(왼쪽으로)
                    for (int j = 0; j < M - 1; j++) {
                        map[num][j] = tmp[j + 1];
                    }
                    map[num][M - 1] = tmp[0];
                    break;
                }
            }
        }
    }

}