알고리즘/코드트리
예술성[G3]
블랑v
2023. 11. 2. 19:41
G3이라고 생각하기 힘들게 어렵게 풀었다.
회전 알고리즘은 메이즈 러너와 유사하다.
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
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;
}