반응형
1.문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
소요시간 : 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();
}
}
}반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [삼성기출 코드트리][Java] 왕실의 기사대결 - 골드3, BFS, 시뮬레이션 (3) | 2024.10.12 |
|---|---|
| [백준 21610][Java] 마법사상어와비바라기 - 골드 5 (0) | 2024.10.10 |
| [삼성기출 코드트리][Java] 마법의숲 탐색 - 골드3 (2) | 2024.10.09 |
| [백준 1926] 그림 - BFS, 실버1 (0) | 2024.10.08 |
| [백준 15683] Java - 감시, 골드3, 시뮬레이션 (0) | 2024.10.06 |