SW 역량 테스트 기출 문제(원판 돌리기)

[원판 돌리기 _ 17822]

 

 

* 조건

1. 배열의 사이즈인 N, M과 명령의 개수(T)가 주어진다
2. 원판에 적힌 수가 주어진다
3. 명령으로는 명령이 진행될 원판의 배수(xi), 방향(di), 회전 수(ki)가 주어진다
4. 방향은 시계 방향(0)과 반시계 방향(1)이다
5. 회전을 진행한 후, 위에 언급된 조건에 맞게 인접한 곳은 모두 0으로 처리한다
6. 만약 한 군데도 인접한 곳이 없다면 전체 원판에 값이 존재하는 값들의 평균을 구해
   • 값 > 평균 -> 값 - 1
   • 값 < 평균 -> 값 + 1
7. 명령을 모두 수행한 후 남아있는 원판 값들의 합을 출력한다

* 알고리즘

• 시뮬레이션
• BFS

* 로직(Logic)

• 주어진 방향에 맞게 해당되는 배열을 회전시킨다
• 회전시킨 후의 맵을 BFS를 통해 인접한 값을 탐색한다
• 탐색을 할 때, 인접한 부분을 0으로 바꿔주는 시기가 중요하다
  (인접한 부분 찾는 과정을 한 번만 하게 되면 원래 인접했던 다음 값들은 체크할 수가 없다)
• 값이 같은 인접 부분은 다시 큐에 넣어줘야 값이 같은 모든 인접한 부분을 0으로 바꿔줄 수 있다
• 만약 인접한 곳을 찾을 수 없다면 원판에 값이 존재하는 곳들의 평균을 구해주고 (조건-6)을 고려한다
• 명령이 끝난 후 최종적으로 존재하는 원판의 합을 출력한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Position_17822 {
    public int y, x;
    public int value;

    public Position_17822(int y, int x, int value) {
        this.y = y;
        this.x = x;
        this.value = value;
    }
}

public class Problem_17822 {

    static int N, M;        //행(원판), 열(원판 내의 값들)
    static int OperNum;     //명령 개수
    static int[][] map;     //원판 맵

    //위 오 아 왼
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        OperNum = Integer.parseInt(st.nextToken());

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

        //명령 수만큼 진행
        for(int i=0; i<OperNum; ++i){
            String operation = br.readLine();
            st = new StringTokenizer(operation, " ");
            int plateNum = Integer.parseInt(st.nextToken());    //원판 배수
            int dir = Integer.parseInt(st.nextToken());         //방향(시계 or 반시계)
            int rotateNum = Integer.parseInt(st.nextToken());   //회전 수

            //회전시키고 -> 인접한지 확인
            doProcess(plateNum, dir, rotateNum);
        }

        //명령이 끝난 후 원판에 남은 값 출력
        int answer = 0;
        for(int i=1; i<=N; ++i){
            for(int j=0; j<M; ++j){
                answer += map[i][j];
            }
        }

        System.out.println(answer);
    }

    private static void doProcess(int plateNum, int dir, int rotateNum) {
        //회전
        for(int i=plateNum; i<=N; i+=plateNum){
            doRotate(i, dir, rotateNum);
        }

        //인접한 부분 찾기
        boolean find = false;
        for(int i=1; i<=N; ++i){
            for(int j=0; j<M; ++j){
                if(map[i][j] > 0){
                    if(findAdjValue(i, j)){
                        find = true;
                    }
                }
            }
        }

        //만약 인접한 곳을 하나라도 못찾았다면 -> 각 원판들의 평균 값을 구하고 값을 비교
        if(!find){
            double avg = getAverage();

            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]++;
                        else if(map[i][j] > avg) map[i][j]--;
                    }
                }
            }
        }
    }
    
    private static void doRotate(int row, int dir, int rotateNum) {
        int r = 0;
        while (r < rotateNum){
            int[] tmp = map[row].clone();

            //시계방향: dir=0
            if(dir == 0){
                //해당 원판을 회전
                map[row][0] = tmp[M-1];
                for(int j=1; j<M; ++j){
                    map[row][j] = tmp[j-1];
                }
            }

            //반시계방향: dir=1
            else if(dir == 1){
                //해당 원판을 회전
                map[row][M-1] = tmp[0];
                for(int j=0; j<M-1; ++j){
                    map[row][j] = tmp[j+1];
                }
            }

            r++;
        }
    }

    /*
        bfs로 탐색
        위, 아래 -> 범위를 벗어나면 안해도 됨
        왼, 오 -> 왼쪽에서 범위를 벗어나면 열의 맨 끝 값을 확인
        오른쪽에서 범위를 벗어나면 열의 맨 앞 값을 확인
    */
    private static boolean findAdjValue(int y, int x) {
        Queue<Position_17822> queue = new LinkedList<>();
        queue.offer(new Position_17822(y, x, map[y][x]));

        boolean check = false;
        while (!queue.isEmpty()){
            Position_17822 q = queue.poll();
            for(int i=0; i<4; ++i){
                int moveY = q.y + dy[i];
                int moveX = q.x + dx[i];

                //좌우 양 끝인 경우
                if(moveX < 0) moveX = M-1;
                else if(moveX >= M) moveX = 0;

                //위 아래의 양 끝인 경우
                if(moveY >=1 && moveY <= N){
                    if(map[moveY][moveX] > 0 && map[moveY][moveX] == q.value){
                        map[moveY][moveX] = 0;
                        queue.offer(new Position_17822(moveY, moveX, q.value));
                        check = true;
                    }
                }
            }
        }

        return check;
    }

    private static double getAverage() {
        int sum=0;
        int 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++;
                }
            }
        }

        double avg = (double) sum / cnt;
        return avg;
    }
}