[BOJ 15686] 드래곤커브

티스토리 에디터가 네이버 블로그처럼 바뀌었다... 예전 에디터보다 UI도 예쁘고 비직관적이었던 아이콘은 없애고 단어로 표현하는 것도 괜찮은 방법인 것 같다

마크다운 문서를 에디터 자체에서 편집할 수 있게 된 것, 코드블럭을 에디터를 통해 삽입할 수 있는 것도 좋다 개발자 친화적 환경 조와용

 

-

 

오늘(?) 푼 문제는 드래곤 커브. 정답률 50% 선을 자랑하는 꽤 쉬운 난이도의 문제지만 접근 방향을 몰라 처음에는 많이 헤멨다. 친절하게 스펙에서 규칙성도 다 가르쳐 줬는데...ㅎㅎㅎㅎㅎㅎㅎ

 

드래곤 커브 문제의 핵심(?)은 그 규칙성을 발견하는 것

도형을 시계 방향으로 90도 회전시켜서 끝점에 위치하게 하는 것은 실제로는 그 끝점을 기준으로 전체 도형을 반시계 방향으로 90도 회전시키는 것과 같다.

그래서 처음에는 각 점을 반시계방향으로 90도 지점에 두는 식을 계산하려고 했더니 넘나 복잡쓰...

 

두번째로 시도한 방법은 각 세대 별로 이동 규칙이 있는지 알아보기 위해서 세대 별 움직임을 기록해 보기로 함

스펙의 예제를 참고해서 드래곤 커브의 이동 규칙을 살펴보면

0세대 : 0

1세대 : 1

2세대 : 2 1

3세대 : 2 3 2 1

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

 

즉 0세대는 주어진 기준대로

1세대는 0세대의 방향 + 1

2세대는 0세대의 반대 방향(+2) 과 1세대의 방향 그대로

3세대는 0+2, 1+2, 2, 1

4세대는 2+2, 3+2, 2+2, 1+2 , 2, 3, 2, 1

 

순서대로 증가하고, 이동하는 개수는 2^(세대 - 1)과 같으며, 딱 절반만큼은 이전 세대와 반대방향으로, 나머지 절반은 이전 세대와 같은 방향으로 증가한다(복잡하다...)

 

다른 분들의 코드를 보면 이 규칙을 더 깔끔하게 정리하셔서 푼 분도 많이 계시던데... 나는 그런거 모르겠고 무조건 if문 썼다...ㅠㅠ 모듈러 연산으로 구현했으면 코드가 더 깔끔하고 읽기 쉬웠을 것 같다. 다음에 이런 규칙성을 발견하는 문제가 나오면 무조건 모듈러 연산을 먼저 고려해보자

정답률 50%인데 나는 이 문제만 거의 3일을 잡고 있었던 것 같다. 중간에 자소서 쓰고 하긴 했지만 순수 풀이시간만 해도 3시간 이상. 실제 코테에서 이 문제가 나왔으면 바로 탈락이다 ^.ㅠ

 

package samsung;

import java.util.*;
import java.lang.*;

class Point{
	int x, y;
	public Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Num15686 {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		Queue<Point> q = new LinkedList<Point>();
		Queue<Integer> direction = new LinkedList<Integer>();
		Queue<Integer> g = new LinkedList<Integer>();
		int x, y;
		for(int i = 0 ; i<n ; i++){
			x = sc.nextInt();
			y = sc.nextInt();
			
			q.add(new Point(x, y));
			direction.add(sc.nextInt());
			g.add(sc.nextInt());
		}
		Queue<Queue<Point>> temp1 = new LinkedList<Queue<Point>>();
		
		for(int i = 0 ; i < n ; i++){
			LinkedList<Point> curves = new LinkedList<Point>();
			LinkedList<Integer> direction2 = new LinkedList<Integer>();

			Point start = q.poll();
			int goal = g.poll();
			int dir = direction.poll();
		
			curves.add(new Point(start.x, start.y));
			for(int j = 0 ; j <= goal ; j++){
				
				if(j == 0){
					switch(dir){
					case 0:
						curves.add(new Point(start.x + 1, start.y));
						direction2.add(0);
						break;
					case 1 :
						curves.add(new Point(start.x, start.y - 1));
						direction2.add(1);
						break;
					case 2 :
						curves.add(new Point(start.x - 1, start.y));
						direction2.add(2);
						break;
					case 3 :
						curves.add(new Point(start.x , start.y + 1));
						direction2.add(3);
						break;
						
					default:
						;
					}
				}
				else if(j == 1){
					Point last = curves.getLast();
					switch(dir){
					case 0:
						curves.add(new Point(last.x , last.y - 1));
						direction2.add(1);
						break;
					case 1 :
						curves.add(new Point(last.x - 1, last.y ));
						direction2.add(2);
						break;
					case 2 :
						curves.add(new Point(last.x, last.y+1));
						direction2.add(3);
						break;
					case 3 :
						curves.add(new Point(last.x + 1, last.y));
						direction2.add(0);
						break;
						
					default:
						;
					}
				}
				else{ // j > 1인 경우
					Iterator<Point> it = curves.iterator();
					
					Point last = curves.getLast();
					
					int size = (int)Math.pow(2, j-1);
					
					int cnt = 0;
					//rotate
					int x1 = last.x;
					int y1= last.y;
					
					while(cnt  < (int)(size / 2)){
						switch(direction2.get(cnt)){
						case 1:
							curves.add(new Point(x1, y1+1));
							direction2.add(3);
							y1 = y1 + 1;
							break;
						case 2:
							curves.add(new Point(x1+1, y1));
							direction2.add(0);
							x1 = x1 + 1;
							break;
						case 3:
							curves.add(new Point(x1, y1-1));
							direction2.add(1);
							y1 = y1 - 1;
							break;
						case 0 :
							curves.add(new Point(x1-1, y1));
							direction2.add(2);
							x1 = x1 - 1;
							break;
						default:
							break;
						}
						cnt++;
					}
					while(cnt < size ) {
						switch(direction2.get(cnt)){
						case 0:
							curves.add(new Point(x1 + 1, y1));
							direction2.add(0);
							x1 = x1 + 1;
							break;
						case 1 :
							curves.add(new Point(x1, y1 - 1));
							direction2.add(1);
							y1 = y1 -1;
							break;
						case 2 :
							curves.add(new Point(x1 - 1, y1));
							direction2.add(2);
							x1 = x1 -1 ;
							break;
						case 3 :
							curves.add(new Point(x1, y1 + 1));
							direction2.add(3);
							y1 = y1+1;
							break;
							
						default:
							;
						}
						cnt++;
					}
					
				}
				dir = direction2.get(j);
			}
			temp1.add(curves);
			
			
		}
		
		Iterator<Queue<Point>> it = temp1.iterator();
		
		int[][] map = new int[102][102];
	
		while(it.hasNext()){
			Queue<Point> tmp = it.next();
			
			while(!tmp.isEmpty()){
				Point tmp2 = tmp.poll();
				map[tmp2.x][tmp2.y] = 1;
			}
		}
		
		int sq = 0;
		
		for(int p = 0 ; p <= 100 ; p++){
			for(int k = 0 ; k <= 100 ; k++){
				if(map[p][k] == 1){ // y, x
					if(map[p][k+1] == 1){
						int a = 0;
					}
					if(map[p][k + 1] == 1 && map[p+1][k] == 1 && map[p+1][k+1] == 1){
						sq += 1;
					}
				}
			}
		}
		
		System.out.println(sq);

		
	}
}