[CodeTree] 예술성(삼성 SW 역량테스트 2022 상반기 오전 2번 문제)

문제

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

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

---

배운 점

- 배열 회전

- 그룹화 DFS

- 그룹별 저장 고민

- 그룹에 대한 카운트 (조합) 

  - 하지만 단순히 조합 Combination으로 풀기엔 너무 많은 경우의 수

  - 필요한 조합만 셀 수 있도록 생각하기

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Set;
import java.util.StringTokenizer;


class Group{
	int cnt;
	int number;

	public Group(int cnt, int number) {
		this.cnt = cnt;
		this.number = number;
	}
}

public class Main{
	static int N, numOfGroup, answer;
	static int[][] board;
	static Group[][] marking;
	static boolean[][] visited;
	static HashMap<Group, Integer> groupAdjCnt;
	static int[][] dxy = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		answer = 0;

		board = new int[N][N];

		// 입력 데이터 전처리
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}


		// 3 번 점수를 측정
		for(int t=0; t < 4; t++) {
			visited = new boolean[N][N];	
			marking = new Group[N][N];


			// 그룹화 및 그룹화 객체를 marking 배열에 저장
			for(int i=0; i < N; i++) {
				for(int j=0; j < N; j++) {
					if(marking[i][j] != null) continue;

					groupMethod(i,j, board[i][j]);
					markGroup(i,j);
				}
			}			

			visited = new boolean[N][N];
			// 그룹화 된 그룹들을 바탕으로 계산 수행
			for(int i=0; i < N; i++) {
				for(int j=0; j < N; j++) {
					if(visited[i][j]) continue;

					groupAdjCnt = new HashMap<>(); // 그룹 하나에 대해서 계산을 수행할 때 초기화
					groupDfs(i, j, marking[i][j]);
					calculateScore(i,j);
				}
			}

			// 끝나면 한번씩 회전을 시켜줘야함.
			board = rotate();
		}

		System.out.println(answer);
	}

	static void groupDfs(int i, int j, Group base) {
		if(i < 0 || j < 0 || i >= N || j >= N || visited[i][j]) return;

		if(marking[i][j] == base) {
			visited[i][j] = true; // 현재 탐색중인 그룹에 대해서만 -> 해당 그룹에 대한 계산은 이번에 끝냄. 4방향 탐색후
			
			for(int d = 0; d < 4; d++) {
				groupDfs(i+dxy[d][0], j+dxy[d][1], base);
			}
		}
		else {
			groupAdjCnt.put(marking[i][j], groupAdjCnt.getOrDefault(marking[i][j], 0) + 1);
			return;
		}
	}

	static void calculateScore(int x, int y) {
		Group base = marking[x][y];
		Set<Group> adjList = groupAdjCnt.keySet();

		for(Group adjGroup : adjList) {
			int score = (base.cnt + adjGroup.cnt) * base.number * adjGroup.number * groupAdjCnt.get(adjGroup);
			if(score != 0) {
				answer += score;
			}
		}
	}

	static int[][] rotate() {
		int[][] rotated = new int[N][N];

		// 1. 십자모양 반시계 회전
		// 십자 가로축 복사 (기존 입력 board 기준 회전)
		for(int i=0; i<N; i++) {
			rotated[(N-1) - i][N/2] = board[N/2][i];
		}
		// 십자 세로축 복사 (기존 입력 board 기준 회전)
		for(int i=0; i<N; i++) {
			rotated[N/2][i] = board[i][N/2];
		}

		// 2. 각 네 구역 시계방향 회전
		rotateQuarter(0, 0, rotated); 
		rotateQuarter(0, N/2+1, rotated); 
		rotateQuarter(N/2+1, 0, rotated); 
		rotateQuarter(N/2+1, N/2+1, rotated); 

		return rotated;
	}

	static void rotateQuarter(int x, int y, int[][] rotated){
		// 반복문의 iterator를 증감 값으로 사용 기본 x,y좌표를 기준
		// 앞서바뀌는 값은 j를 통해 조작, 이후 느리게 바뀌는값은 i를 통해 조작
		for(int i = 0; i < N/2; i++) {
			for(int j = 0; j < N/2; j++) {
				rotated[x+i][y+j] = board[x+(N/2-1)-j][y+i];
			}
		}
	}

	static void groupMethod(int i, int j, int num) {
		if(i < 0 || j < 0 || i >= N || j >= N) return;
		if(visited[i][j] || board[i][j] != num) return;		

		visited[i][j] = true;

		for(int d = 0; d < 4; d++) {
			groupMethod(i+dxy[d][0], j+dxy[d][1], num);
		}
	}


	static void markGroup(int x, int y) {
		int cnt = 0;
		int num = board[x][y];


		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(visited[i][j]) cnt++;
			}
		}

		Group group = new Group(cnt, num);

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(visited[i][j]) {
					marking[i][j] = group;
					visited[i][j] = false;
				}
			}
		}
	}


}

---

풀이

1. 메서드 정리

메서드 명	역할	비고
main	- 입력데이터 전처리 - turn 별 과정 진행 - simulation 메서드 호출
void groupDfs(int i, int j, Group base)	- 인자로 넘어온 i, j 를 기준으로 해당 인덱스가 포함되는 그룹에 대해 인접 그룹을 조사 - 다른 칸에서 이미 조사했을 수 있으므로 visited 여부 판별 후 조사 시작 - 인자로 넘어온 base와 같은 경우엔 같은 그룹이므로 visited 처리 및 상하좌우 방향으로 이동  - 인자로 넘어온 base와 다른 경우엔 인접 타그룹이므로 HashMap 에 저장 -> getOrDefault 메서드로 키 추가 및 값 누적
void calculateScore(int x, int y)	- 문제에서 제시된 점수 계산 로직 반영
int[][] rotate()	- 십자모양 90도 반시계 회전 - 각 사분면 90도 시계 회전   - rotateQuarter라는 별도의 메서드 추가해서 사용
void rotateQuarter(int x, int y, int[][] rotated)	- 각 사분면에 대한 90도 시계 회전 진행 - 인자로 시작점 좌표 및 rotated 배열을 받아 인덱스 계산해서 반영
void groupMethod(int i, int j, int num)	- 2차원 배열을 탐색하면서 각 번호별로 그룹핑을 진행하는 메서드  - 해당 메서드에서 visited로 처리해놓으면 markGroup 메서드를 통해 Group 객체를 추가해 marking 배열에 인스턴스 추가
void markGroup(int x, int y)	- markGroup 메서드는 groupMethod에서 visited처리를 해놓은 영역들에 대해서 cnt 값(그룹을 이루는 칸의 수) 을 세고, 이후 Group 객체를 만들어 marking 배열에 저장한다. - 처리가 끝나면 visited 값은 false로 돌려놓는다.

 

2. 시뮬레이션 반복 로직 설명

해당 문제의 경우 아래와 같은 순서로 4번 for문을 돌려 풀이했습니다.

 

1. turn 마다 사용할 visited 배열 및 marking 배열을 초기화

2. 입력으로 들어온 초기 배열에서 숫자별로 groupMethod를 통해 그룹화를 시키고 각각의 그룹에 대하여 Group 객체를 배열에 저장하면서 마킹 by. markGroup (이때 marking 2차원 배열내 각 그룹별 영역에 저장되는 Group객체는 동일 주소값을 공유 = 같은 객체 -> 얕은복사)

3. 이후 visited 배열을 다시 초기화하고 각 그룹을 돌면서 인접한 변의 개수를 구함.

  3.1. dfs를 통해 탐색하면서 해당 그룹에서 방문한 곳은 visited 처리 -> 방문한 순간 인접한 칸들에 대해 다른 그룹인지를 체크하고 해당 그룹을 key 값으로 가지는 HashMap<Group, Integer> groupAdjCnt 에 숫자를 저장 

  3.2. 이후 해당 해쉬맵에 저장된 값들을 이용해 base 그룹에 대해 인접한 score를 검사. 

  (**참고) 단, visited 처리는 base 그룹에 대해서만 진행합니다. 이후 다른 그룹에서는 앞서 인접 그룹을 체크한 group에 대해서는 점수를 세지 않아도 되므로 -> 배열을 차근차근 읽으며 걸리는 group에 대해서 인접배열을 체크하는대신 이후에는 다시 체크하지 않도록 함.

4. 이후 turn을 넘기기전 board 에 대해 가운데선 반시계회전, 각 사분면 시계방향 90도 회전을 적용(by. rotate())

 

3. 주요 메서드 코드 설명

3.1. groupDfs

	static void groupDfs(int i, int j, Group base) {
		if(i < 0 || j < 0 || i >= N || j >= N || visited[i][j]) return;

		if(marking[i][j] == base) {
			visited[i][j] = true; // 현재 탐색중인 그룹에 대해서만 -> 해당 그룹에 대한 계산은 이번에 끝냄. 4방향 탐색후
			
			for(int d = 0; d < 4; d++) {
				groupDfs(i+dxy[d][0], j+dxy[d][1], base);
			}
		}
		else {
			groupAdjCnt.put(marking[i][j], groupAdjCnt.getOrDefault(marking[i][j], 0) + 1);
			return;
		}
	}

 

- main 메서드에서 2중 for문을 돌며 board의 전체 배열을 탐색시킨다. 

  - 탐색하면서 해당 영역이 visited 처리가 되었는지 판별하고 이후 방문하지 않았다면 검사하지 않은 그룹으로 분류해 해당 영역을 검사한다.

  - groupDfs 메서드는 그런 상황에서 인자로 들어온 좌표값에 해당하는 원소에 대해 그룹화 시켜 해당 그룹이 같은 그룹인지 판별하고 이후 다른 그룹에 대해서는 인접하고 있다고 판단해서 groupAdjCnt (HashMap<Group, Integer>) 에 값을 올린다. 

  - 이때 Group을 key값으로 사용하여 base 그룹에 대해 인접한 Group의 변의 값이 저장되게 된다. 

  - 이를 위해 2차원 Group 타입 배열 marking을 선언해두었고 해당 좌표에 있는 Group객체를 marking 배열로 부터 얻어와 비교할 수 있다.

- getOrDefault 메서드도 오랜만에 사용해봤는데 너무 오랜만에 사용해서 거의 처음본 메서드인 느낌이다. 

  - 첫번째 인자로 key를 입력하고 두 번째 인자로 초기값을 입력한다.

  - 만일 해당하는 키값이 있다면 value를 가져오고, 없다면 두번째인자인 0을 가져오게된다. 

  - 해당 사용법을 잘 숙지하고 여러모로 잘 사용할 것 같은 메서드이다.

 

3.2. rotateQuarter

	static void rotateQuarter(int x, int y, int[][] rotated){
		// 반복문의 iterator를 증감 값으로 사용 기본 x,y좌표를 기준
		// 앞서바뀌는 값은 j를 통해 조작, 이후 느리게 바뀌는값은 i를 통해 조작
		for(int i = 0; i < N/2; i++) {
			for(int j = 0; j < N/2; j++) {
				rotated[x+i][y+j] = board[x+(N/2-1)-j][y+i];
			}
		}
	}

- 각 사분면(?) 이라고 표현하는게 맞는지 모르나 생긴건 사분면이다. 해당 영역들에 대해서 시계방향 90도 변환하는 메서드이다.

- 해당 인덱싱을 쉽게 이해할 수 있는 방법은 두 개의 for문의 시작이 인자로들어온 x, y 가 아니고 , 시작점(좌측 최상단 좌표)을 기준으로 값을 증감시키는 역할로 사용된다고 생각하면 회전 로직이 쉽게 느껴진다.