코드 트리 - 예술성(45번)

❓ 문제 - 코드 트리(code tree) 예술성 45번 - JAVA 풀이법

 

출처

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

코드트리

 

 

📝 문제해결법

1. 문제

• 각 map에 적힌 숫자와 인접한 것으로 그룹을 형성하고, 그 그룹간의 주어진 식을 이용해서 예술성 점수를 구하는 문제이다.
• 그러나 예술성 점수를 구하는 과정에서 총 3번의 회전이 이루어지는데, 한 번은 십자가의 위치한 부분의 90도 반시계 회전이고, 십자가를 제외한 부분의 4부분 영역의 90도 시계 회전이 일어난다.

 

2. 해결 방법

• 문제의 구현을 크게 4부분으로 나눠서 해결한다.
  • 초기 예술성 -> 1번의 회전 -> 2번의 회전 -> 3번의 회전 이며 각 과정에서 예술성 점수를 누적해서 구해준다.
  • 각 파트 부분에서는 (초기회전이 아닌 경우라면) 십자가 회전 -> (초기회전이 아닌 경우라면) 십자가 제외 부분 회전 -> 그룹핑 -> 그룹핑된 것을 기준으로 예술점수 구하기로 구현 흐름을 잡을 수 있다.
• 십자가 회전
  
  • 일단 map2로 map의 정보를 복사하며 회전 처리를 한 후에 다시 map에 값을 넣어준다.
  • 반시계 회전이므로 일단 세로 영역 부분을 가로영역으로 값을 복사해줄 때 세로 영역(열이 n/2로 고정), 가로 영역(행이 n/2로 고정)으로 인덱스를 잘 조정해서 구해준다.
  • 가로 영역 부분을 세로 영역으로 값을 복사해줄 때 가로영역(행이 n/2로 고정), 세로 영역(열이 n/2로 고정)됨을 잘 코드에 구현한다.

public static void rotate1() {
		int[][] map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				map2[i][j] = map[i][j];
			}
		}
		
		// 십자 모양 (세로->가로)
		for(int i=0;i<n;i++) {
			int j = n/2;
			map[j][i] = map2[i][j];
		}
		
		// 십자 모양 (가로->세로)
		for(int j=0;j<n;j++) {
			int i = n/2;
			map[n-j-1][i] = map2[i][j];
		}
	}

 

• 십자가 이외의 영역의 회전
  • 우선 각 4부분이 시계방향 회전을 하므로, 기존에 배열에서 90도 시계 회전을 구현할 때 예시는 다음과 같다.

public class Main {
	
	public static void main(String[] args) {
		int[][] arr = {
				{1, 0, 0},
				{1, 1, 1},
				{1, 0, 1},
				{1, 0, 1}
		};
		
		int n = arr.length;
		int m = arr[0].length;
		int[][] rotate = new int[m][n];
		
		for(int i=0;i<rotate.length;i++) {
			for(int j=0;j<rotate[i].length;j++) {
				rotate[i][j] = arr[n-1-j][i];
			}
		}
		
		for(int i=0;i<rotate.length;i++) {
			for(int j=0;j<rotate[i].length;j++) {
				System.out.print(rotate[i][j] +" ");
			}
			System.out.println();
		}
		
	}

}

• 이것을 십자가로 나누어진 4영역에 맞추어서 인덱스를 잘 조정하면 다음과 같이 구할 수 있다.

public static void rotate2() {
		int[][] map2 = new int[n][n];
		int nn = n/2;
        // 십자가 왼쪽 위
		for(int i=0;i<n/2;i++) {
			for(int j=0;j<n/2;j++) {
				map2[i][j] = map[n-1-j-nn-1][i];
			}
		}
		// 십자가 오른쪽 위
		for(int i=0;i<n/2;i++) {
			for(int j=n/2+1;j<n;j++) {
				map2[i][j] = map[n-1-j][i+nn+1];
			}
		}
		// 십자가 왼쪽 아래
		for(int i=n/2+1;i<n;i++) {
			for(int j=0;j<n/2;j++) {
				map2[i][j] = map[n-1-j][i-nn-1];
			}
		}
		// 십자가 오른쪽 아래
		for(int i=n/2+1;i<n;i++) {
			for(int j=n/2+1;j<n;j++) {
				map2[i][j] = map[n-1-j+nn+1][i];
			}
		}

		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i == n/2 || j == n/2) continue;
				map[i][j] = map2[i][j];
			}
		}
		
	}

 

• 그룹핑
  • bfs를 통해 그룹핑하며, g_map을 통해 그룹핑된 그룹의 숫자를 저장하며 이것을 bfs내에 방문체크에도 활용한다.
  • 만약 4방향으로 인접한 곳이 같은 값이라면 같은 그룹으로 묶도록 구현한다.
  • 그룹핑 후, 해당 그룹에 포함된 칸 수를 카운트 해서 group_list에 그룹의 번호, 그룹의 포함 갯수에 대한 정보를 넣어줘서 예술성 점수를 구할 때 활용한다.

	public static int grouping(int x, int y, int g_num, int num) {
		int cnt = 0;
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));
		cnt++;
		g_map[x][y] = g_num;
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int i=0;i<4;i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >=n || ny < 0 || ny >= n) continue;
				if(g_map[nx][ny] != 0 || map[nx][ny] != num) continue;
				g_map[nx][ny] = g_num;
				cnt++;
				q.add(new Node(nx, ny));
			}
		}
		return cnt;
	}

 

• 예술성 점수 구하기
  • 따로 조합을 통해 예술성 점수를 구할 두 개의 그룹을 정하는 것보다, 그냥 2차원 배열을 쭉 탐색하면서 해당 칸을 4방향으로 탐색했을 때 다른 그룹에 속한다면 예술성 점수를 구하는 식을 활용해서 점수를 구하고 해당 값들을 누적해서 더해주면 된다.
  • 그리고 마지막에 2로 나눠주는데 이게 그룹 1에서 그룹2에 대한 예술성점수를 구하면, 그룹 2에서 그룹1에 대한 예술성 점수를 다시 한번 구하기 때문에 중복을 제거하기 위해 2로 나눠준다.

public static int getScore() {
		int score = 0;
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				for(int d=0;d<4;d++) {
					int nx = i + dx[d];
					int ny = j + dy[d];
					if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if(g_map[i][j] == g_map[nx][ny]) continue;
					int g1 = g_map[i][j];
					int g2 = g_map[nx][ny];
					int g1_c = group_list.get(g1-1).c;
					int g2_c = group_list.get(g2-1).c;
					int g1_n = group_list.get(g1-1).num;
					int g2_n = group_list.get(g2-1).num;
					score += (g1_c+g2_c)*g1_n*g2_n;
				}
			}
		}
		return score/2;
	}

 

3. 느낀점

• 오랜만에 알고리즘을 풀었는데 문제를 정확히 안 봐서 구현을 여러번 수정했다.. 앞으로 문제 3번은 읽어볼 것 ! 특히 삼성기출은 꼭꼭!!
• 그리고 십자가 회전을 처음에 그냥 map을 90도 회전하고 그것을 십자가 영역만 값을 복사해주는 형태로 진행했는데 효율성을 위해 십자가 영역 부분을 인덱스에 잘 맞추어서 값을 복사해주도록 구현했다.
• 그리고 두 그룹의 예술성점수를 구할 때 map이 변경될 때마다 구해진 그룹의 총 수로 두 그룹의 조합을 구해서 예술성 점수를 구하도록 했는데 너무 비효율적이었다. 그래서 다른 사람들의 코드를 보니 조합을 이용하지 않고 그냥 2차원 배열로 각 칸을 기준으로 4방향의 인접한 곳이 다른 그룹이라면 계속 예술성 점수를 누적해서 구하도록 했고 실제로 구현하니 시간적으로 500ms -> 100ms로 줄었다.
• 앞으로 그냥 통과되도록 구현하는 것보다는,  조금 더 시간 단축할 수 있는 구간을 체크해서 시간적인 효율성도 고려해야겠다.

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_45 {
	public static int n, g_cnt;
	public static int[][] map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static ArrayList<int[]> combi;
	public static int[][] g_map;
	public static ArrayList<Node> group_list;
	
	public static class Node {
		int x;
		int y;
		int c;
		int num;
		
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		public Node(int x, int y, int c, int num) {
			this.x = x;
			this.y = y;
			this.c = c;
			this.num = num;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
	
		
		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 sum = 0;
		for(int i=0;i<=3;i++) {
			
			if(i != 0) {
			// 십자기 회전
				rotate1();
			// 십자기 밖 회전
				rotate2();
			}
			g_map = new int[n][n];
			group_list = new ArrayList<>();
			combi = new ArrayList<>();
			g_cnt = 0;
			
			for(int p=0;p<n;p++) {
				for(int q=0;q<n;q++) {
					if(g_map[p][q] == 0) {
						g_cnt++;
						int c = grouping(p, q, g_cnt, map[p][q]);
						group_list.add(new Node(p, q, c, map[p][q]));
					}
				}
			}

			// 예술 점수 구하기
			int score = getScore();
			sum += score;
		}

		System.out.println(sum);
		
	}
	
	public static int getScore() {
		int score = 0;
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				for(int d=0;d<4;d++) {
					int nx = i + dx[d];
					int ny = j + dy[d];
					if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if(g_map[i][j] == g_map[nx][ny]) continue;
					int g1 = g_map[i][j];
					int g2 = g_map[nx][ny];
					int g1_c = group_list.get(g1-1).c;
					int g2_c = group_list.get(g2-1).c;
					int g1_n = group_list.get(g1-1).num;
					int g2_n = group_list.get(g2-1).num;
					score += (g1_c+g2_c)*g1_n*g2_n;
				}
			}
		}
		return score/2;
	}
	
	public static int grouping(int x, int y, int g_num, int num) {
		int cnt = 0;
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(x, y));
		cnt++;
		g_map[x][y] = g_num;
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int i=0;i<4;i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >=n || ny < 0 || ny >= n) continue;
				if(g_map[nx][ny] != 0 || map[nx][ny] != num) continue;
				g_map[nx][ny] = g_num;
				cnt++;
				q.add(new Node(nx, ny));
			}
		}
		return cnt;
	}
	
	public static void rotate1() {
		int[][] map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				map2[i][j] = map[i][j];
			}
		}
		
		// 십자 모양 (세로->가로)
		for(int i=0;i<n;i++) {
			int j = n/2;
			map[j][i] = map2[i][j];
		}
		
		// 십자 모양 (가로->세로)
		for(int j=0;j<n;j++) {
			int i = n/2;
			map[n-j-1][i] = map2[i][j];
		}
	}
	
	public static void rotate2() {
		int[][] map2 = new int[n][n];
		int nn = n/2;
		for(int i=0;i<n/2;i++) {
			for(int j=0;j<n/2;j++) {
				map2[i][j] = map[n-1-j-nn-1][i];
			}
		}
		
		for(int i=0;i<n/2;i++) {
			for(int j=n/2+1;j<n;j++) {
				map2[i][j] = map[n-1-j][i+nn+1];
			}
		}
		
		for(int i=n/2+1;i<n;i++) {
			for(int j=0;j<n/2;j++) {
				map2[i][j] = map[n-1-j][i-nn-1];
			}
		}
		
		for(int i=n/2+1;i<n;i++) {
			for(int j=n/2+1;j<n;j++) {
				map2[i][j] = map[n-1-j+nn+1][i];
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i == n/2 || j == n/2) continue;
				map[i][j] = map2[i][j];
			}
		}
		
	}
	


}