백준 17822 원판 돌리기 (Java,자바)

jonghyukLee·2021년 11월 4일

이번에 풀어본 문제는
백준 17822번 원판 돌리기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point
{
    int x,y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
public class Main{
    static int N,M,T;
    static List<Integer>[] map;
    static int [] mv;
    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 List[N+1];
        mv = new int[4];

        //상 하 좌 우
        mv[0] = 1;
        mv[1] = -1;
        mv[2] = 1;
        mv[3] = M - 1;

        for(int i = 0; i <= N; ++i) map[i] = new LinkedList<>();

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

        for(int i = 0; i < T; ++i)
        {
            st = new StringTokenizer(br.readLine());
            rotate(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
        int answer = 0;
        for(List<Integer> i : map)
        {
            for(int j : i)
            {
                answer += j;
            }
        }
        System.out.print(answer);
    }
    static void rotate(int x, int d, int k)
    {
        int len = k;
        if(d == 0) len = M - k;

        for(int i = x; i <= N; i+=x)
        {
            List<Integer> tmp_list = map[i].subList(0,len);
            map[i].addAll(tmp_list);
            map[i].subList(0,len).clear();
        }
        check();
    }
    static void check()
    {
        int total = 0;
        int cnt = 0;
        boolean flag = false;
        Set<Point> set = new HashSet<>();
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 0; j < M; ++j)
            {
                int cur = map[i].get(j);
                if(cur > 0)
                {
                    total += cur;
                    cnt++;
                    for(int idx = 0; idx < 2; ++idx) // 상하
                    {
                        int mx = i + mv[idx];

                        if(!isValid(mx) || map[mx].get(j) < 1) continue;
                        if(cur == map[mx].get(j))
                        {
                            flag = true;
                            set.add(new Point(i,j));
                            set.add(new Point(mx,j));
                        }
                    }

                    for(int idx = 2; idx < 4; ++idx) // 좌우
                    {
                        int my = (j + mv[idx]) % M;
                        if(map[i].get(my) > 0)
                        {
                            if(cur == map[i].get(my))
                            {
                                flag = true;
                                set.add(new Point(i,j));
                                set.add(new Point(i,my));
                            }
                        }
                    }
                }
            }
        }
        if(!flag)
        {
            double ave = (double)total/cnt;
            for(int i = 1; i <= N; ++i)
            {
                for(int j = 0; j < M; ++j)
                {
                    int cur = map[i].get(j);
                    if(cur > 0)
                    {
                        if(cur > ave) map[i].set(j,cur-1);
                        else if(cur < ave) map[i].set(j,cur+1);
                    }
                }
            }
        }
        else
        {
            for(Point cur : set)
            {
                map[cur.x].set(cur.y,0);
            }
        }

    }
    static boolean isValid(int x)
    {
        return x > 0 && x <= N;
    }
}

📝 풀이

원판을 주어진 횟수, 조건에 맞게 회전시킨 후 남은 값의 총합을 구하는 문제입니다.
먼저 회전을 수행한 이후 인접한 위치에 같은 값이 있을 경우, 값을 제거해주고, 없는 경우에는 남은 수들의 평균값을 구해 작다면 +1, 크다면 -1을 해줍니다.
먼저 삽입/삭제가 잦을 것 같아 LinkedList 형태의 배열을 사용했고, 반시계 방향을 기준으로 잡았을때 시작 위치부터 회전횟수(K)개 만큼 리스트를 잘라주고 뒤에 그대로 붙여주면 회전을 수행할 수 있습니다. 시계방향의 경우 숫자의 갯수인 M - K 를 해주면 됩니다.
회전을 수행한 이후에는 상,하,좌,우 인접한 값을 체크하여 값이 같다면 Set에 add해줍니다. 바로바로 삭제했을 경우 삭제된 값을 기준으로 인접한 값들을 체크할 수 없어서 이 방법을 선택했고, 중복된 값을 제외하기 위해 Set을 활용했습니다.
flag가 false라면 동일한 값을 한번도 만나지 못한 경우이므로 평균값을 구해 주어진 조건에 맞게 값들을 수정해줍니다.
위의 반복을 T번 수행한 후 마지막 탐색으로 값을 누적하여 더해주면 해결됩니다.