Baekjoon[17822] - 원판 돌리기

링크

17822번: 원판 돌리기

문제설명

• 시뮬레이션 + 연결성 탐색

문제풀이

• 연결성 탐색 = DFS, BFS

문제코드

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

public class Main17822 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Ans=0;
    public static int N;
    public static int M;
    public static int T;
    public static LinkedList<Integer>[] circle;
    public static LinkedList<int[]> q;

    public static void move(int idx, int dir, int num) {
//        시계방향 1 1 2 3 -> 3 1 1 2
        if(dir==0) {
            for (int i = 0; i < num; i++) {
                circle[idx].addFirst(circle[idx].pollLast());
            }
        }
//        반시계방향 1 1 2 3 -> 1 2 3 1
        else {
            for (int i = 0; i < num; i++) {
                circle[idx].addLast(circle[idx].pollFirst());
            }
        }
    }

    public static void query() {

//        1번쿼리
        int nr;
        int nc;
        int nowval;
        int[] nowrc;
        boolean removed_total=false;
        boolean removed;
        for (int i = 1; i <=N ; i++) {
            for (int j = 0; j < M; j++) {
                nowval = circle[i].get(j);

                if(nowval!=0) {
//                    BFS 탐색
                    q.add(new int[] {i,j});
//                    circle[i].set(j, 0);    // 다끝나고 처리해주는걸로
                    removed = false;
                    while(!q.isEmpty()) {
                        nowrc = q.poll();
                        for (int d = 0; d < 4; d++) {
                            nr = nowrc[0] + dir[d][0];
                            nc = nowrc[1] + dir[d][1];
                            nc = (nc+M)%M;    //원형

                            if(nr>=1 && nr<=N && nc>=0 && nc<M && circle[nr].get(nc)==nowval) {
                                removed = true;
                                q.add(new int[] {nr,nc});
                                circle[nr].set(nc,0); 
                            }
                        }
                    }

                    if(removed) {
                        circle[i].set(j, 0);
                        removed_total=true;
                    }
                }
            }
        }

//        2번쿼리
        if(!removed_total) {
            int cnt=0;
            int sum=0;
            int n;
            for (int i = 1; i <= N; i++) {
                for (int j = 0; j < M; j++) {
                    n = circle[i].get(j);
                    if(n!=0) {
                        cnt++;
                        sum+=n;
                    }
                }
            }
            double avg = (double)sum/(double)cnt;
            for (int i = 1; i <= N; i++) {
                for (int j = 0; j < M; j++) {
                    n = circle[i].get(j);
                    if(n!=0) {
                        if(n>avg) {
                            circle[i].set(j, n-1);
                        }
                        else if(n<avg) {
                            circle[i].set(j, n+1);
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/17822.txt"));
        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 LinkedList[N+1];
        for (int i = 1; i <= N; i++) {
            circle[i] = new LinkedList<Integer>();
        }

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

        int x,d,k;
        q = new LinkedList<int[]>();

        for (int c = 0; c < T; c++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            for (int i = 1; i <= N; i++) {
                if(i%x==0) {
                    move(i,d,k);
                }
            }

            query();
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                Ans+=circle[i].get(j);
            }
        }

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• 연결성 탐색 방식을 1칸만 탐색했었는데, 2번째 테케 보다보니 연결이 더 넓게 퍼질수 있음.
  • 4방만 탐색했었음
  • BFS로 탐색
• ArrayList로 회전을 구현했었는데, List접근하는것 보다 Array 접근하는게 훨씬 속도가 빠를것 같다. 안해봐서 모르겠는데.

잘한점

• O(N)
  • 맵크기 * query갯수 * (회전 + 연결성 탐색) = 50*50*(max(50*50,50*50)) = 50^4 = 6*10^6
  • 안터짐
• ArrayList index 1~N인것 안헷갈리고 경계검사 잘 씀
• 회전 연결성은 nr = (nr+M)&M 으로 잘 처리함