[Unsolved][JAVA] 코드트리 예술성

https://www.codetree.ai/frequent-problems/artistry/description

코드트리

 

1. 서론

 

dfs + 배열 돌리기 + 시뮬레이션... 궁극기 같은 문제인데 무려 '보통'이시랜다. (피눈물...)

시간 안에 못 푼 것은 물론이요, 풀이 방법 그나마 떠올린 것마저 죄다 틀림. 난 bfs여야 하는 줄 ㅠ 배열도 제대로 못 돌림,,,,

 

2. 문제 풀이

 

2차원 배열이 주어진다. 그 배열 안에는 숫자가 적혀있는데 한 군데에 뭉쳐있는 같은 숫자들끼리 그룹을 만들어야 한다.

그리고 각 그룹 쌍을 만들어 예술점수를 매기려고 한다.

 

예술 점수 공식: (그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수

 

예술 점수를 이런 식으로 적용한다고 할 때, 초기 예술 점수 + 1회 차 예술 점수 + 2회 차 예술 점수 + 3회 차 예술 점수의 값을 구하는 문제이다. 이때 회차는 중간에 배열을 돌리기 때문에 회차라고 붙는다.

 

돌리는 방법

1: 2차원 배열의 십자 방향만 반시계 방향으로 90도 방향으로 돌림

2: 2차원 배열의 십자로 나눠진 4구역 각각 시계방향으로 90도 돌림

 

 

 

 

결국 프로세스는 이렇다.

 

초기 그룹 나눔 -> 초기 예술점수 매김

-> 배열 돌리기 1,2 -> 그룹 다시 나눔 -> 1회 차 예술 점수

-> 배열 돌리기 1,2 -> 그룹 다시 나눔 -> 2회 차 예술 점수

-> 배열 돌리기 1,2 -> 그룹 다신 나눔 -> 3회 차 예술 점수

 

반복되는 부분은 반복문을 돌리면 되고 여러 번 쓰는 함수를 따로 만들어줬다.

//그룹을 나누는 함수, 예술점수를 매기는 함수, 배열 돌리는 함수 1, 배열 돌리는 함수2

 

그런데 나는 그룹 나누는 함수 bfs로 짜려고 하다가 구현을 못해서 배열 돌리는 함수나 구현해야지 했는데 그것도 잘 안됐다. 그냥 전체가 아니라 구역이 나누어져 있기 때문에 쉽지 않았다. 솔직히 이번에도 너무 숫자 끼워 맞추기라 재활용 불가일 듯...

 

아이디어 자체는 비슷했다. 나 같은 경우에는 초기에 기준값을 정하고 bfs로 같은 숫자가 나오는 부분만 탐색하고 칸의 수를 재고 그 부분 탐색이 끝나면 빠져나오고 이걸 그룹수만큼 반복하려 했다. 근데 어떻게 그 그룹을 구분할까 고민했지만 방법이 생각이 안 났고, 코드도 내 생각처럼 구분이 안돼 결국 답을 보게 되었다.

 

나는 원래 bfs로 돌리다가 다른 숫자 나오면 그 닿은 변 쌍으로 저장하고, 나중에 쓰려고 했는데 일단 경곗값이 여러 개이기 때문에 경곗값만 가지고는 그룹 번호를 부여할 수 없었다... 닿은 변의 수도 bfs로 구해야지 생각했는데 닿은 변의 수는 사실상 구하지 않아도 됐다.

 

답은 dfs로 탐색했고(bfs도 안되지는 않지 않을까?), 그룹을 구분하는 방법은 2차원 배열을 따로 만들어서 그 안에 원래의 배열에 고유의 숫자가 적혀있는 부분을 그룹 번호로 적어서 구분해줬다. (어떻게 보면 간단한 건데 왜 생각을 못했을까) 그리고 이 작업은 dfs로 돌기 때문에 경곗값을 만날 때마다 반복되므로 따로 닿은 변의 수를 구해서 곱해주지 않아도 됐다.(생각지도 못한 부분 ㅜㅜ)

 

 

 

 

 

3. 코드 설명

 

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

public class Main {
	
	static int n, ans, gn;
	static int[][] map, tmp, group; //그룹번호를 적는 배열
	static int[] dx = {-1, 1, 0, 0}, dy = { 0, 0, 1, -1}, gcnt; //동서남북, 그룹마다 차지하는 칸 수
	static boolean[][] visit;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	for (int j = 0; j < n; j++)
        		map[i][j] = Integer.parseInt(st.nextToken());
        }
        
        tmp = new int[n][n];
        
        for (int i = 0; i < 4; i++) {//초기 + 1 + 2 + 3
        	grouping();
        	calc();
        	if (i == 3) break;//마지막 이후는 배열 안 돌려도 됨
        	rotation1();
        	rotation2();
        }
        
        System.out.println(ans);
       
    }
    
    public static void dfs(int x, int y) {
    	for (int i = 0; i < 4; i++) {
    		int nx = x + dx[i], ny = y + dy[i];
    		if (range(nx, ny) && !visit[nx][ny] && map[x][y] == map[nx][ny]) {//같은 그룹에 대해서
    			visit[nx][ny] = true;
    			group[nx][ny] = gn; //그 그룹번호를 적어서 그룹을 나누고
    			gcnt[gn]++; //그룹칸 수 세어줌
    			dfs(nx, ny);
    			
    		}
    	}
    }
    
    public static void grouping() { //그룹을 만들어줌
    	visit = new boolean[n][n];
        group = new int[n][n];
        gcnt = new int[n * n + 1];
        gn = 0;
    
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (!visit[i][j]) {//한 그룹의 기준값
    				gn++;
    				visit[i][j] = true;
    				group[i][j] = gn;
    				gcnt[gn] = 1;
    				dfs(i, j);
    			}
    		}
    	}
    }
    
    public static void calc() { //점수 계산
    	int sum = 0;
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			for (int k = 0; k < 4; k++) {
    				int nx = i + dx[k] , ny = j + dy[k];
    				if (range(nx, ny) && map[i][j] != map[nx][ny]) {//경계값이 다른 경우(즉,서로 맞닿아있는 만큼 반복)
    					int g1 = group[i][j], g2 = group[nx][ny]; // 각 그룹 번호를 구함
    					int num1 = map[i][j], num2 = map[nx][ny]; //각 그룹 고유 숫자를 구함
    					int cnt1 = gcnt[g1], cnt2 = gcnt[g2]; //각 그룹이 몇 개의 칸인지 구함
    					
    					//그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값
    					sum += (cnt1 + cnt2) * num1 * num2;
    				}
    			}
    		}
    	}
    	
    	ans += sum / 2; //(g1, g2), (g2, g1) 경우 중복 방지
    }
   
    public static void rotation1() { //반시계방향
    	copy(tmp, map);
    	
    	for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++) {
                // Case 2 - 1. 세로줄에 대해서는 (i, j) -> (j, i)가 됩니다.
                if(j == n / 2)
                	tmp[j][i] = map[i][j];
                // Case 2 - 2. 가로줄에 대해서는 (i, j) -> (n - j - 1, i)가 됩니다.
                else if(i == n / 2)
                    tmp[n - j - 1][i] = map[i][j];
            }
    	
    	copy(map, tmp);
    }
   
   public static void rotation2() {//시계방향
	   copy(tmp, map);
	   
	   //1섹션
	   for (int i = 0; i < n / 2; i++)
		   for (int j = 0; j < n / 2; j++)
	            tmp[i][j] = map[n / 2 - 1 - j][i];
	 
	   //2섹션
	    for (int i = 0; i < n / 2; i++)
	    	for (int j = n / 2 + 1; j < n; j++)
	            tmp[i][j] = map[n - 1 - j][n / 2 + 1 + i];
	    //3섹션
	   for (int i = 0; i < n / 2; i++)
	    	for (int j = n / 2 + 1; j < n; j++)
	    		tmp[n/ 2 + 1 + i][n / 2 * 2 - j] = map[j][i];
	    
	    //4섹션
	   for (int i = n / 2 + 1; i < n; i++)
	    	for (int j = 0; j < n / 2; j++)
	            tmp[i][j + n / 2 + 1] = map[n - 1 - j][i];
	    
	    copy(map, tmp);
   }
    
    public static boolean range(int nx, int ny) {
    	if (nx >= 0 && nx < n && ny >= 0 && ny < n)
    		return true;
    	return false;
    }
    
    public static void copy(int[][] a, int[][] b) {
    	for (int i = 0; i < n; i++)
        	for (int j = 0; j < n; j++)
        		a[i][j] = b[i][j];
    }
}

 

최대한 친절하게 주석을 적었다.

rotation1은 원래 짰었는데 십자는 잘 도는데 이상하게 주변 값도 건드려져서 그냥 해설에 있는 것 썼고 rotation2는 

 

https://jaeyoon8783.tistory.com/67

배열 시계방향, 반시계방향 돌리기

 

이 블로그를 보고 가져왔는데 4 섹션으로 나눠서 돌려야 하기 때문에 i, j값을 대공사로 바꿔야 해서 적용이 막 되지는 않았다. (그냥 노가다로 합침)

 

 

 

+ 봐야 할 것, dfs, bfs 코드들, 배열 돌리기 코드