[삼성SW테스트] 드래곤 커브 15685(백준)

삼성 SW테스트

#15685 - 드래곤 커브(Dragon Curve)

https://www.acmicpc.net/problem/15685

사용한 개념

1. 음...규칙찾기?(수열과 같은 느낌)

처음 이런류의 문제를 시뮬레이션이라 부른다고 합니다.. 백준 알고리즘 카테고리에는 시뮬레이션으로 분류되어있네요~

문제를 이해하셨다면 아시겠지만, 분명 세대가 증가할때마다, 이전 세대와의 어떠한 규칙이 있음을 의심하고 그 규칙을 찾는것이 제일 먼저 선행 되어야 합니다. 보통 대게 이런문제가 규칙을 찾고 그 규칙대로 구현을 하면 되는 문제인 것 같습니다.

자.. 그럼 규칙을 찾아보겠습니다. 저는 무식하지만 제일 간단한 접근방법인 한단계씩 적어서 어떠한 규칙이 있는지 파악하겠습니다.

다음과 같이 방향이 주어질때, 0 방향으로 4세대까지 진행될 때, 어떠한 방향으로 그리는지 확인해봅시다.

0 (→), 1 (↑), 2 (←), 3 (↓) 

0 세대 : 0

1 세대 : 0 1 

2 세대 : 0 1 2 1

3 세대 : 0 1 2 1 2 3 2 1

4 세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

반드시 직접 0방향으로 시작해서 4세대까지 그려진 그림을 보고 위와 같이 방향을 알아내야 쉽습니다. 자 눈치 채셨나요? 이전세대까지 진행된 점들에 대해 역방향으로 그려지고 있습니다. 

즉, 시계 방향으로 90도 돌리지만, 이는 이전 세대들의 점들에 대해 반시계방향으로 90도를 그리고 있습니다. 

규칙을 더욱 명확하게 그리면.... 

3 인경우, 4방향은 없으니 다시 0으로 줘야합니다. (반 시계방향으로 생각해보시면 됩니다. ↓ - →)

이제 규칙을 구했으니, 전체적인 알고리즘을 바로 구현하면 되는데요... 저는 아래와 같은 플로우로 알고리즘을 구현해보았습니다.

1. 방향정보를 설정하고 저장한다!

2. 시작점에서 드래곤 커브를 그릴때, 방향정보대로 그려나간다. 

3. input된 모든 시작점에 대해 1.2.를 반복한다.

4. 모든 시작점에 대해 드래곤커브를 그렸다면, 그려진 2차원 배열을 하나씩 탐색하며 4개의 꼭지점이 모두 드래곤커브에 해당되는지 체크한다.

상세한 내용에 대해선 아래 코드에 주석해놨습니다. 

혹시 궁굼하신 점 있으시면 언제든 댓글남겨주세요~

package SamsungTest;

import java.util.ArrayList;
import java.util.Scanner;

public class DragonCurve {

	static int[][] map = new int[101][101];
	//배열 방향정보 : 0 (→), 1 (↑), 2 (←), 3(↓), 4(대각선아래)
	static int[] goX = {0,-1,0,1,1};
	static int[] goY = {1,0,-1,0,1};
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int curveNum = sc.nextInt();
		
		int[][] curveInfoArray = new int[curveNum][4];
		
		for(int i=0; i<curveNum; i++){
			for(int j=0; j<4; j++){
				curveInfoArray[i][j] = sc.nextInt();
			}
		}

		solutions(curveInfoArray);

	}
	
	
	private static void solutions(int[][] curveInfoArray) {
	
		for(int i=0; i<curveInfoArray.length; i++){
			ArrayList<Integer> direction = new ArrayList<>();
			direction.add(curveInfoArray[i][2]);
			for(int j=0; j<curveInfoArray[i][3]; j++){
				
				//이동해야할 방향을 설정한다.
				int size = direction.size();
				for(int k=size-1; k>=0; k--){
					int n = direction.get(k);
					if(n==3){
						direction.add(0);
					}else{
						direction.add(n+1);
					}
				}
			}
			
			//시작지점부터 방향설정에 따라 그린다.
			drawing(curveInfoArray[i][0], curveInfoArray[i][1], direction);
		}
			//4개  꼭지점이 모두 선택된 사각형을 탐색
			countRec();
	
	}
	
	private static void countRec() {
		int result = 0;
		//100인 이유 마지막 행과 열은 애초에 사각형을 이룰 수 없기 떄문에 검사하지 않는다.
		for(int i=0; i<100; i++){
			for(int j=0; j<100; j++){
				// 0(→) 3 (↓) 4 (대각선 아래)
				if(map[i][j]==1 && map[i+goX[0]][j+goY[0]]==1 && map[i+goX[3]][j+goY[3]]==1 && map[i+goX[4]][j+goY[4]]==1){
					result++;
				}
			}
		}
		
		System.out.println(result);
		
	}

	private static void drawing(int x, int y, ArrayList<Integer> direction) {
		map[y][x] = 1;
		for(int i=0; i<direction.size(); i++){
			y = y+goX[direction.get(i)];
			x = x+goY[direction.get(i)];
			map[y][x] = 1;
		}

	}



}