https://www.acmicpc.net/problem/17822
오래간만에 만나는 구현 문제입니다. 반갑지는 않습니다.
풀이
복잡한 단계의 작업을 쪼개서 풀었습니다. 다만 조금 신경을 써줘야 하는 조건들이 있습니다.
1. 돌리기 단계
Deque 자료 구조를 활용하였습니다. 시계 방향인 경우 맨 마지막 요소를 맨 앞으로 넣어주었습니다.
* x 의 배수인 원판을 모두 돌려야 합니다
2. 중복 찾기
탐색이 시작이 가능한 모든 정점에 그래프의 탐색과 다를 것 없이 상하좌우로 탐색을 해주었습니다.
* 0번 인덱스와 마지막 인덱스가 서로 붙어있는 것을 주의해야 합니다!
3. 중복이 없는 경우
중복이 없는 경우에는 원판에 남아있는 요소의 평균값과 비교를 통해 그 값보다 크면 -1 작으면 +1을 해줘야 합니다.
* 평균이 정수가 아닌 경우까지 생각을 해줘야 합니다!
* 평균값을 쉽게 알기 위해서 현재 원판에 남아있는 정수의 합과 빠진 값의 수를 탐색 중 업데이트해주었습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Num17822원판돌리기 {
static int n,m,t,nums;
static int[] dx = {1,0,-1,0}, dy={0,-1,0,1};
static private class Loca{
int r,c;
Loca(int r, int c){
this.r = r;
this.c = c;
}
}
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());
List<List<String>> map = new ArrayList<>();
int sum = 0;
nums = n*m;
for(int i=0;i<=n;i++){
map.add(new ArrayList<>());
if(i == 0) continue;
st = new StringTokenizer(br.readLine());
for(int j=0;j<m;j++){
String value = st.nextToken();
sum += Integer.parseInt(value);
map.get(i).add(value);
}
}
while(t >0){
st = new StringTokenizer(br.readLine());
int target = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
int originTarget = target;
while(target<=n){
List<String> newList = roll(map.get(target),dir,count);
map.remove(target);
map.add(target,newList);
target += originTarget;
}
int removeValue = 0;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(!map.get(i).get(j).equals("N")) removeValue += search(map,i,j);
}
}
if(removeValue == 0 && nums != 0 ){
int average = sum/nums;
boolean isDouble = false;
if(average * nums < sum) isDouble = true;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(!map.get(i).get(j).equals("N")){
if(Integer.parseInt(map.get(i).get(j)) > average){
int value = Integer.parseInt(map.get(i).get(j)) -1;
sum --;
map.get(i).set(j,String.valueOf(value));
}else if(Integer.parseInt(map.get(i).get(j)) < average){
int value = Integer.parseInt(map.get(i).get(j)) +1;
sum ++;
map.get(i).set(j,String.valueOf(value));
}else{
if(isDouble){
int value = Integer.parseInt(map.get(i).get(j)) +1;
sum ++;
map.get(i).set(j,String.valueOf(value));
}
}
}
}
}
}else{
sum -= removeValue;
}
t--;
}
// System.out.println(nums);
System.out.println(sum);
}
public static List<String> roll(List<String> numbers, int direction, int count){
Deque<String> deque = new LinkedList<>();
deque.addAll(numbers);
while(count > 0){
if(direction == 0){
deque.addFirst(deque.pollLast());
}
if(direction == 1){
deque.addLast(deque.pollFirst());
}
count--;
}
List<String> newList = new ArrayList<>();
newList.addAll(deque);
return newList;
}
public static int search(List<List<String>> map,int r, int c){
String value = map.get(r).get(c);
int removeCnt = 1;
int removeValue = Integer.parseInt(value);
Queue<Loca> que = new LinkedList<>();
que.add(new Loca(r,c));
while(!que.isEmpty()){
Loca now = que.poll();
for(int i=0;i<4;i++){
int nxtR = now.r + dx[i];
int nxtC = now.c +dy[i];
if(nxtC >= m) nxtC = 0;
if(nxtC == -1) nxtC = m-1;
if(nxtR>0 && nxtR<=n && nxtC>=0 && nxtC <m && !map.get(nxtR).get(nxtC).equals("N") && map.get(nxtR).get(nxtC).equals(value)){
map.get(r).set(c,"N");
removeCnt++;
removeValue += Integer.parseInt(value);
map.get(nxtR).set(nxtC,"N");
que.add(new Loca(nxtR,nxtC));
}
}
}
if(removeCnt == 1){
return 0;
}
nums -= removeCnt;
return removeValue;
}
}