예술성[G3]

 

G3이라고 생각하기 힘들게 어렵게 풀었다.

회전 알고리즘은 메이즈 러너와 유사하다.

 

https://www.codetree.ai/training-field/frequent-problems/problems/artistry/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

package codeTree;

/*
이게 왜 G3일까? 엣지가 없어서인듯 여기서 외워야 할 것
반시계 방향 회전 : //rotated[row][col] = original[col][N-1-row]
시계 방향 : rotated[row][col] = original[N-1-col][row]
*/


import java.util.*;
import java.io.*;
public class G3_Artistry_rebuild2 {
	
	static int N, res;
	static Field[][] map;
	static boolean[][] visit;
	static List<Group> groups = new ArrayList<>();
	
	static final int[] DR = {-1, 0, 1, 0}; //URDL
	static final int[] DC = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		setting();
		
		int C = 4; //3회 반복
		while(C > 0) {
			setField();
			score();
			clean(); //세탁 과정 필요
			rotate(); //배열 돌리기
			C--;
		}

//		log();
		System.out.println(res / 2);
	}
	
	static void rotate() {
		cross(); //십자 돌리기
		square(); //정사각형 돌리기
	}
	
	static void square() {
		//4개의 정사각형 좌표 찾기
		int size = N / 2;
		
		//각 정사각형 돌리는 로직 재활용
		rotateSquare(new Pos(0, 0) ,size);
		rotateSquare(new Pos(0, N - size) ,size);
		rotateSquare(new Pos(N - size, 0) ,size);
		rotateSquare(new Pos(N - size, N - size) ,size);
	}
	
	static void rotateSquare(Pos start, int size) {
		//좌상좌하, 길이 좌표값 가져옴
		//rotated[row][col] = original[col][N-1-row]
		
		int[][] before = new int[size][size]; //원본
		
		//원본 가져오기
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				before[i][j] = map[i + start.r][j + start.c].fieldNo; 
			}
		}
		
		//적용하기
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				map[i + start.r][j + start.c].fieldNo = before[size - 1 - j][i]; 
			}
		}
	}
	
	static void cross() {
		//N의 크기에 따라 달라짐, N은 무조건 홀수
		//맵 중앙에서 뻗어나가는 URDL을 전부 저장했다가, 자리에 넣어두기
		int size = N / 2;
		int center = map[size][size].fieldNo;
		int[][] URDL = new int[4][size];
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < size; j++) {
				int nr = size + (DR[i] * (j + 1));
				int nc = size + (DC[i] * (j + 1));
				URDL[i][j] = map[nr][nc].fieldNo;
			}
		}
		
		//URDL -> 한칸씩 밀기 (회전) -> RDLU
		int[] temp = URDL[0]; //U 보관
		URDL[0] = URDL[1];
		URDL[1] = URDL[2];
		URDL[2] = URDL[3];
		URDL[3] = temp;
		
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < size; j++) {
				int nr = size + (DR[i] * (j + 1));
				int nc = size + (DC[i] * (j + 1));
				map[nr][nc].fieldNo = URDL[i][j];
				
			}
		}
	}
	
	static void clean() {
		//맵 groupNo 초기화
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j].groupNo = -1;
			}
		}
		
		visit = new boolean[N][N];
		groups = new ArrayList<Group>();
	}
	
	static void score() {
		for(int i = 0; i < groups.size(); i++) {
			Group now = groups.get(i);
			getScore(now);
		}
	}
	
	static void getScore(Group now) {
		//같지 않은 값의 groupNo를 탐색해서 추가해야 할 듯
		HashMap<Integer, Integer> hm = new HashMap<>();
		Queue<Integer> keys = new ArrayDeque<>(); //HM key values
		
		visit = new boolean[N][N];
		Queue<Pos> bfs = new ArrayDeque<>();
		bfs.add(now.firstPos);
		
		//사방탐색해서 groupNo랑 다른 칸을 찾고, 해당 칸의 groupNo별로 hm에 매핑
		int nowGroupNo = now.groupNo;
		while(!bfs.isEmpty()) {
			Pos pos = bfs.poll();
			if(visit[pos.r][pos.c] && map[pos.r][pos.c].groupNo == nowGroupNo) continue; //방문 처리
			visit[pos.r][pos.c] = true;
			
			//만약 이 좌표가 우리 그룹과 다른 GroupNo라면 조건 수행
			if(nowGroupNo != map[pos.r][pos.c].groupNo) {
				int thisNo = map[pos.r][pos.c].groupNo; //다른 인접그룹넘버;
				if(hm.containsKey(thisNo)) {
					hm.put(thisNo, hm.get(thisNo) + 1);
				}
				else {
					keys.add(thisNo);
					hm.put(thisNo, 1);
				}
				continue;
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = pos.r + DR[i];
				int nc = pos.c + DC[i];
				if(cantGo(nr, nc) || (visit[nr][nc] && map[nr][nc].groupNo == nowGroupNo)) continue;
				bfs.add(new Pos(nr, nc));
			}
		}
		

		int nowRes = 0; //여기 결과값
		while(!keys.isEmpty()) {
			int key = keys.poll();			
			Group other = groups.get(key);
			int between = hm.get(key); //맞닿은 변의 수
//			System.out.println(now.groupNo + " 에서 " + other.groupNo+ "과의 관계(각 칸, 맟닿은 변) : " + now.kan + " : "+other.kan + ", " + between);
			nowRes += getScore(now.kan, now.fieldNo, other.kan, other.fieldNo, between);
		}
		
		res += nowRes;
	}
	
	static int getScore(int aKan, int aField, int bKan, int bField, int between) {
		int cnt = 0;
		//(a칸 수 + b칸의 수 ) x a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수
		cnt = (aKan + bKan) * aField * bField * between;
		return cnt;
	}
	
	static void setField() {
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j].groupNo == -1) grouping(i, j, cnt++);
			}
		}
	}
	
	static void grouping(int r, int c, int no) {
		//그룹 추가
		Group now = new Group();
		now.firstPos = new Pos(r, c);
		now.groupNo = no;
		now.fieldNo = map[r][c].fieldNo;
		
		//map 변환 : -1 탐색
		int kanCount = 0; //칸
		Queue<Pos> bfsQueue = new ArrayDeque<>();
		bfsQueue.add(new Pos(r, c));
		while(!bfsQueue.isEmpty()) {
			Pos pos = bfsQueue.poll();
			if(map[pos.r][pos.c].groupNo != -1 || map[pos.r][pos.c].fieldNo != now.fieldNo) continue;
			map[pos.r][pos.c].groupNo = no; //그룹핑
			kanCount++; //칸 카운트 증가
			
			for(int i = 0; i < 4; i++) {
				int nr = pos.r + DR[i];
				int nc = pos.c + DC[i];
				
				if(cantGo(nr, nc) || map[nr][nc].groupNo != -1 || map[nr][nc].fieldNo != now.fieldNo) continue;
				bfsQueue.add(new Pos(nr, nc));
			}
		}
		
		now.kan = kanCount;
		groups.add(now); //그룹 리스트 추가
	}

	static void log() {
		System.out.println();
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j].fieldNo + " ");
			}
			System.out.println();
		}
		System.out.println("===================");
		System.out.print("칸카운트  : " );
		for(int i = 0; i < groups.size(); i++) {
			Group now = groups.get(i);
			System.out.print(" " + now.kan);
		}
		System.out.println();
		System.out.println("===================");
	}
	static boolean cantGo(int r, int c) {
		if(r < 0 || c < 0 || r >= N || c >= N) return true;
		return false;
	}
	
	static void setting() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		map = new Field[N][N];
		visit = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = new Field();
				map[i][j].fieldNo = Integer.parseInt(st.nextToken());
				map[i][j].groupNo = -1; //그룹 미지정
			}
		}
	}
}

class Pos {
	int r, c;
	Pos() {}
	Pos(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

class Field {
	int fieldNo;
	int groupNo;
}

class Group {
	int fieldNo;
	int groupNo;
	Pos firstPos;
	int kan;
}