[JAVA] 백준 원판 돌리기

탐색+구현 문제이다.

 

탐색 방식은 BFS방식으로 Queue에 넣어서 방향을 검사하는 것이다.

좌표값을 Queue에 넣는 방식을 새로 소개하겠다.

 

Queue<int[]> q = new LinkedList<>();
q.add(new int[]{i, j, map[i][j]});

위의 코드처럼 Queue의 자료형에 배열을 넣어주면 임의의 배열을 통째로 넣을 수 있다.

따라서 위에서는 int[] = (x, y, 비교할 해당값) 을 큐에 넣어준 것이다.

 

그럼 위와 같은것을 언제 사용하는가?

=> 이중for문을 통해서 map을 한번 다 탐색하고 나서 다시 또 그 값을 찾아가야할때.

 

---

테스트케이스1 예시

문제의 remove를 할때 탐색을 해서 bfs나 dfs를 통해 이웃하는 숫자의 값을 지워야한다.

백트래킹 방식으로 끝부분부터 지워야 탐색을하는데 지장이 없다.

 

전체코드는 아래와 같다.

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

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

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            rotate(x, d, k);
            if (!remove())
                replace();
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1)
                    ans += map[i][j];
            }
        }
        System.out.println(ans);
    }

    private static void replace() {
        int sum = 0, cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1) {
                    sum += map[i][j];
                    cnt++;
                }
            }
        }
        double avg = sum / (double) cnt;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1) {
                    if ((double) map[i][j] > avg)
                        map[i][j]--;
                    else if ((double) map[i][j] < avg)
                        map[i][j]++;
                }
            }
        }
    }

    private static boolean remove() {
        boolean flag = false;
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1 || visit[i][j])
                    continue;
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i, j, map[i][j]});
                visit[i][j] = true;
                while (!q.isEmpty()) {
                    int[] now = q.poll();
                    for (int k = 0; k < dr.length; k++) {
                        int nr = now[0] + dr[k];
                        int nc = now[1] + dc[k];

                        if (nr < 0 || nr >= N)
                            continue;

                        if (nc == -1)
                            nc = M - 1;
                        else if (nc == M)
                            nc = 0;
                        if (visit[nr][nc])
                            continue;
                        if (map[nr][nc] == now[2]) {
                            visit[nr][nc] = true;
                            q.add(new int[]{nr, nc, now[2]});
                            map[now[0]][now[1]] = -1;
                            map[nr][nc] = -1;
                            flag = true;
                        }
                    }
                }
            }
        }
        return flag;
    }

    private static void rotate(int x, int d, int k) {
        for (int r = 0; r < N; r++) {
            if ((r + 1) % x != 0)
                continue;
            if (d == 0) {
                // 시계방향 회전
                for (int times = 0; times < k; times++) {
                    // k 칸 이동
                    int[] tmp = map[r].clone();
                    map[r][0] = tmp[M - 1];
                    for (int i = 1; i < M; i++) {
                        map[r][i] = tmp[i - 1];
                    }
                }
            } else {
                // 반시계 방향 회전
                for (int times = 0; times < k; times++) {
                    // k 칸 이동
                    int[] tmp = map[r].clone();
                    map[r][M - 1] = tmp[0];
                    for (int i = 0; i < M - 1; i++) {
                        map[r][i] = tmp[i + 1];
                    }
                }
            }
        }
    }

}