[백준] 원판 돌리기

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

 

풀이과정

1. 원판을 회전시키는 함수를 구현해야 합니다.

ArrayList 혹은 LinkedList를 사용해서 구현할 수 있습니다.
add, insert ,remove 함수를 활용하여 원판의 회전을 구현할 수 있습니다. 

 

2. 원판에서 인접한 숫자들 끼리 일치여부를 확인해야 합니다.

dfs를 통해 인접여부를 구현합니다. 인접하게 되면 -1로 원소를 변경하여 체크했습니다.

 

이때 같은 원판 내에서의 순회(?)를 구현해줘야 합니다.

예를들어 [2,3,4,2] 와 같은 원판인 경우 제일 앞 원소 2와 제일 뒤 원소 2는 인접해 있습니다. 따라서 dfs수행 중 인덱스가 -1이 되면 3으로, 4가 되면 0으로 보정을 해줘야 합니다.

static boolean check(int r, int c, int val){

        int flag = 0; // 일치 여부를 확인하기 위한 변수

        for(int d=0;d<4;d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
			
            // 같은 원판내 순회를 구현
            if(nc==-1) nc = M-1;
            if(nc==M) nc = 0;

            if(nr>=1 && nr<=N && circle[nr].get(nc)==val){
                circle[nr].set(nc,-1); // -1로 표시
                check(nr,nc,val); // dfs 수행
                flag = 1;
            }
        }

        if(flag==1) return true; // 일치 된 원소가 있는 경우 true 리턴
        return false;

    }

또한 dfs를 시작한 위치에도 -1로 표시를 해주기 위해 일치 여부에 따른 true와 false를 리턴하도록 구현했습니다.

// 2. 지울 숫자 체크
int flag = 0;
            for(int i=1;i<N+1;i++){
                for(int j=0;j<M;j++){
                    if(circle[i].get(j)==-1) continue;
                    if(check(i,j,circle[i].get(j))){
                        circle[i].set(j,-1); // 현재 위치도 지우기
                        flag = 1;
                    }
                }
            }

true 즉 일치한 경우가 있으면 현재위치 (i,j)도 -1로 표시를 해줬습니다.

 

3. 전체 원판의 갱신 여부에 따른 업데이트를 진행해야 합니다.

// 2. 지울 숫자 체크
            int flag = 0;
            for(int i=1;i<N+1;i++){
                for(int j=0;j<M;j++){
                    if(circle[i].get(j)==-1) continue;
                    if(check(i,j,circle[i].get(j))){
                        circle[i].set(j,-1); // 현재 위치도 지우기
                        flag = 1;
                    }
                }
            }

            // 3. 지워진 숫자 여부에 따라 원판 업데이트
            if(flag==0){
                update();
            }

 

2번 코드와 이어지는 코드 입니다.

지워진 경우가 없으면 update를 진행해줍니다. 이때 평균값 계산에 double 변수를 사용해줘야 합니다.

static void update(){
        double avg = 0;
        int sum = 0;
        int cnt = 0;
        for(int i=1;i<N+1;i++){
            for(int j=0;j<M;j++){
                if(circle[i].get(j)==-1) continue;
                sum += circle[i].get(j);
                cnt += 1;
            }
        }
        avg = (double)sum / cnt;

        for(int i=1;i<N+1;i++){
            for(int j=0;j<M;j++){
                int val = circle[i].get(j);
                if(val==-1) continue;
                if(val < avg){
                    circle[i].set(j,val+1);
                }else if(val > avg){
                    circle[i].set(j,val-1);
                }
            }
        }

    }

평균 계산 후 업데이트 하는 함수

알게된 점

• ArrayList와 LinkedList
  • 조회(get)시에는 ArrayList가 성능이 좋고, 삽입/삭제(add/remove) 시에는 LinkedList가 성능이 좋습니다.

연산	LinkedList	ArrayList
첫번째 위치에 insert / remove	O(1)	O(N)
마지막 위치에 insert / remove	O(1)	O(1) 혹은 O(N)
인덱스로 값 get	O(N)	O(1)

• ArrayList의 첫번째 삽입이 O(N) 인 이유는 요소들을 뒤로 이동시켜야 하기 때문입니다.
• 또한 ArrayList의 마지막 위치 삽입이 O(1) 혹은 O(N)인 이유는 만약 공간이 부족하면 배열 복사로 인한 시간 소요때문 입니다.
• 그런데,, 실제로 LinkedList는 잘 사용되지 않는다고 합니다. 성능면에서 체감상 둘이 큰 차이가 없다고 합니다
• 처음 Deque를 사용해서 원판 회전을 구현하려 했는데, Deque에는 get 메소드가 없어서 구현에 실패했습니다. 그래서 계속 다른 접근법으로 문제를 풀어나갔는데,, ArrayList의 insert, remove 메소드를 사용하여 문제를 해결할 수 있음을 알게되었습니다.

 

전체코드

package com.mincheolsong;
import java.util.*;
import java.io.*;

public class Main {

    static int N,M,T;
    static List<Integer>[] circle;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};

    static void rotate(int X, int D, int K){

        if(D==0){ // 시계 방향이면, 제일 뒤에 원소를 제일 앞으로
            int x = X;
            while(x < N+1){
                for(int k=0;k<K;k++){
                    int back_e = circle[x].remove(circle[x].size()-1);
                    circle[x].add(0,back_e);
                }
                x += X;
            }

        }else if(D==1){ // 반시계 방향이면, 제일 앞의 원소를 제일 뒤로
            int x = X;
            while(x < N+1){
                for(int k=0;k<K;k++){
                    int front_e = circle[x].remove(0);
                    circle[x].add(front_e);
                }
                x += X;
            }
        }
    }

    static boolean check(int r, int c, int val){

        int flag = 0;

        for(int d=0;d<4;d++){
            int nr = r + dr[d];
            int nc = c + dc[d];

            if(nc==-1) nc = M-1;
            if(nc==M) nc = 0;

            if(nr>=1 && nr<=N && circle[nr].get(nc)==val){
                circle[nr].set(nc,-1);
                check(nr,nc,val);
                flag = 1;
            }
        }

        if(flag==1) return true;
        return false;

    }

    static void update(){
        double avg = 0;
        int sum = 0;
        int cnt = 0;
        for(int i=1;i<N+1;i++){
            for(int j=0;j<M;j++){
                if(circle[i].get(j)==-1) continue;
                sum += circle[i].get(j);
                cnt += 1;
            }
        }
        avg = (double)sum / cnt;

        for(int i=1;i<N+1;i++){
            for(int j=0;j<M;j++){
                int val = circle[i].get(j);
                if(val==-1) continue;
                if(val < avg){
                    circle[i].set(j,val+1);
                }else if(val > avg){
                    circle[i].set(j,val-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());
        circle = new List[N+1];
        for(int i=1;i<N+1;i++){
            circle[i] = new LinkedList<>();
        }

        for(int n=1;n<=N;n++){
            st = new StringTokenizer(br.readLine());
            for(int m=0;m<M;m++){
                circle[n].add(Integer.parseInt(st.nextToken()));
            }
        }

        for(int t=0;t<T;t++) {
            st = new StringTokenizer(br.readLine());
            int X, D, K;
            X = Integer.parseInt(st.nextToken()); // 원판 번호(x의 배수)
            D = Integer.parseInt(st.nextToken()); // 0 : 시계, 1 : 반시계
            K = Integer.parseInt(st.nextToken()); // k칸

            // 1. 회전
            rotate(X,D,K);

            
            // 2. 지울 숫자 체크
            int flag = 0;
            for(int i=1;i<N+1;i++){
                for(int j=0;j<M;j++){
                    if(circle[i].get(j)==-1) continue;
                    if(check(i,j,circle[i].get(j))){
                        circle[i].set(j,-1); // 현재 위치도 지우기
                        flag = 1;
                    }
                }
            }
            
            // 3. 숫자가 지워진 여부에 따라 원판 업데이트
            if(flag==0){
                update();
            }

          

        }

        int ans = 0;

        for(int i=1;i<=N;i++){
            for(int j=0;j<M;j++){
                int val = circle[i].get(j);
                if(val==-1) continue;
                ans += val;
            }
        }

        System.out.println(ans);

    }
}