[삼성기출 코드트리][Java] 예술성 - 골드3, bfs, 구현

1.문제

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

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

 

소요시간 : 2h 50m

 

4분할 배열돌리기 빡세다 ...

 

풀이는 추후에 정리해서 올리겠음요 

package boj;

import java.io.*;
import java.util.*;

public class CT예술성 {
	static int n;
	static int[][] map;
	static boolean[][] visit;
	static int[][] group;
	static int score;
	static ArrayList<Integer> cnt_list;
	static ArrayList<Integer> val_list;
	static int dx[] = {0,0,-1,1};
	static int dy[] = {1,-1,0,0};
	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());
		map = new int[n][n];
		visit = new boolean[n][n];
		group = new int[n][n];
		cnt_list = new ArrayList<>();
		val_list = new ArrayList<>();
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int total =0;
		total += getArt();
		
		for(int i=0;i<3;i++) {
			rotate();
			smallRotate();
			visit = new boolean[n][n];
			group = new int[n][n];
			cnt_list = new ArrayList<>();
			val_list = new ArrayList<>();
			total += getArt();
			
		}
	
		System.out.println(total);
		//printMap();
	}
	private static int getArt() {
		int group_cnt=0;
		int ans=0;
		group_cnt = getCnt();
				
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				
				for(int l=0;l<4;l++) {
					int nx = i + dx[l];
					int ny = j + dy[l];
					int g1= group[i][j] ;
				
					if(!check(nx,ny)) continue;
					int g2= group[nx][ny] ;
					
					if (map[i][j]!=map[nx][ny]) {
						ans += (cnt_list.get(g1) + cnt_list.get(g2)) * val_list.get(g1) * val_list.get(g2);
					}
				}
			
			}
		}
		ans = ans/2;
		//System.out.println("시도: "+ans);
		return ans;
		
	}
	
	private static void rotate() {
		int[][] map2 = new int[n][n];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
					map2[i][j] =  map[j][n-1-i];
			}	
		}
		
		int num = n/2;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i==num || j==num)
					map[i][j] =  map2[i][j];
			}
				
		}
	}
	//시계 90 
	private static void smallRotate() {
	    int num = n / 2;  // 가운데 십자 모양을 제외하기 위한 중간 지점
	    
	    int[][] map2 = new int[n][n];
	    
	    // 왼쪽 위 사분면 내에서 회전
	    for (int i = 0; i < num; i++) {
	        for (int j = 0; j < num; j++) {
	            map2[i][j] = map[ n - 1 - j - num -1 ][i];  // 시계방향 회전 공식
	        }
	    }
	    
	    // 오른쪽 위 사분면 내에서 회전
	    for (int i = 0; i < num; i++) {
	        for (int j = num + 1; j < n; j++) {
	            map2[i][j] = map[n- 1 - j][i + num+1];
	        }
	    }
	    
	    // 왼쪽 아래 사분면 내에서 회전
	    for (int i = num + 1; i < n; i++) {
	        for (int j = 0; j < num; j++) {
	            map2[i][j] = map[n - 1 -j ][i-num-1];
	        }
	    }
	    
	    // 오른쪽 아래 사분면 내에서 회전
	    for (int i = num + 1; i < n; i++) {
	        for (int j = num + 1; j < n; j++) {
	            map2[i][j] = map[n - 1 - j + num+1 ][i];
	        }
	    }

	    // 회전한 값들을 map에 복사
	    for (int i = 0; i < n; i++) {
	        for (int j = 0; j < n; j++) {
	            if (!(i == num || j == num)) {  // 가운데 십자 부분은 제외
	                map[i][j] = map2[i][j];
	            }
	        }
	    }
	}

	
	private static int getCnt() {
		int cnt=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(!visit[i][j]) {
					bfs(i,j,cnt);
					
					cnt++;
					}
			}
		}
		
		return cnt;
	}

	private static void bfs(int x, int y, int c) {
	
		
		visit[x][y] = true;
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {x,y});
		int val=1; //각 그룹이 가지고 있는 갯수 
		group[x][y]=c;
		
		while(!que.isEmpty()) {
			int[] arr = que.poll();
			int arrx = arr[0];
			int arry = arr[1];
			
			for(int i=0;i<4;i++) {
				int nx = arrx+dx[i];
				int ny = arry+dy[i];
				
				//범위벗어나거나 이미 봤으면 실패 ;
				if(!check(nx,ny)|| visit[nx][ny]) continue;
				
				if(map[nx][ny]==map[arrx][arry]) {
					group[nx][ny]=c;
					val++;
					que.offer(new int[] {nx,ny});
					visit[nx][ny] = true;
				}
					
			}
			
		}
		
		//System.out.println("val: "+val);
		cnt_list.add(val);
		val_list.add(map[x][y]);
		
	}
	private static boolean check(int x, int y) {
		if(x<0||x>=n||y<0||y>=n) return false;
		return true;
	}
	private static void printMap() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				System.out.print(map[i][j]+ " ");
				//System.out.print(group[i][j]+ " ");
			}
			System.out.println();
		}
			
	}

}