15685 드래곤 커브

 

첫번째 예제를 가지고 설명을 해본다.

3
3 3 0 1
4 2 1 3
4 2 2 1

 

여기서 두번째 예제 4 2 1 3 를 설명해보면,

4가 세로 방향이고, 2가 가로 방향이라고 했으므로

(2,4) 인 상황을 생각해보겠다.

 

일단 방향은 아래와 같다. 

0 : 오른쪽 →

1 : 위 ↑

2 : 왼쪽 ←

3 : 아래 ↓

 

 

 

1. 차수  0

 

그러면 차수가 0일 때의 상황은 아래와 같다. 

(2,4)에서 위쪽으로 올라간다.

 

 

2. 차수  1

 

 

끝 점인 (1,4) 을 기준으로 시계방향으로 90도 회전하면 왼쪽 방향이 된다.

즉 (1,4)에서 (1,3)으로 이동

3. 차수 2

 

위의 도형을 끝점 기준으로 시계방향으로 회전시, 아래와 같다. 

 

 

4. 차수 3

 

마지막으로 아래와 같이 완성된다. 

 

 

그러면 위의 그림에서 규칙성을 찾을 수 있다.

 

<1>  (2,4) -> (1,4) 방향의 파랑색 화살표

차수 3의 상황에서 시계방향 회전하면

(4,3) -> (4,2) 방향의 파랑색 화살표처럼 방향이 바뀌는데, 

각 파랑색 화살표의 방향은 

위쪽(↑) 방향 -> 왼쪽(←) 왼쪽 방향

 

<2> (1,4) -> (1,3) 방향의 연보라색 화살표 

왼쪽(←) 방향 -> 아래쪽(↓) 방향

..

 

즉, 시계 반대 방향으로 90도 회전한 상태로 바뀐다. 

 

각 차수마다 위와 같은 상황이 생긴다.

 

1) 즉, 첫번째에서 (차수 0 ) 에서는 

 

=> 위 방향

 

2) 두번째 ( 차수 1) 에서는 

 

=> 위 방향, 왼쪽 방향

 

차수 2, 차수 3에서도 마찬가지이다.

 

그리고 시계 방향 반대는 원래 값 + 1을 하면 된다.

 

즉, 방향을 나타내는 값이 아래와 같은데,

 

0 : 오른쪽 →

1 : 위 ↑

2 : 왼쪽 ←

3 : 아래 ↓

 

위방향 -> 왼쪽 방향

1 + 1 = 2

 

이런식으로 진행된다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {	
	
	static boolean map[][];
	
	public static void main(String[] args) throws IOException {		
	
		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	      map = new boolean[101][101];	   
	      int K = Integer.parseInt(st.nextToken());
	      
	      while(K-->0) {
	    	  
	    	  st = new StringTokenizer(br.readLine(), " ");
	    	  int x =  Integer.parseInt(st.nextToken());
	    	  int y = Integer.parseInt(st.nextToken());
	    	  int d = Integer.parseInt(st.nextToken());
	    	  int g = Integer.parseInt(st.nextToken());
	    
	    	 ArrayList<Integer> direction =  getDirection(y, x, d,g);
	    
	    	 solve(y,x, direction);    	  
	    	  
	      }
	            
	      int count = 0;
	      
	      for(int i=0; i<100; i++) {
	    	  for(int j=0; j<100; j++) {    		  
	    		  
	    		  if(map[i][j] && map[i][j+1] && map[i+1][j] && map[i+1][j+1]) {
	    			  count++;
	    			  
	    		  }	    		  
	    	  }
	      }
	       
	      
	      System.out.println(count);     
	      
	    }
	
	
	public static ArrayList<Integer> getDirection(int a, int b, int d, int generation) {		
		
			
		ArrayList<Integer> list = new ArrayList<>();
		list.add(d);		
		
		// 세대 바뀔 때마다 
		while(generation -->0) {		
			
			for(int i = list.size()-1; i>=0 ; i--) {		
				
				// 현재 방향
				int direction = list.get(i);			
				
				// 다음 방향 
				direction = (direction +1) % 4;
				list.add(direction);	
				
			}			
		}		
		
		return list;	
	}
	
	
	
	
	public static void solve(int a, int b, ArrayList<Integer> directionList) {
				
		map[a][b] = true;	
		
		for(int direction : directionList) {
			
			// 오른쪽
			if(direction == 0) {			
				
				b++;
				
			// 위쪽
			}else if(direction ==1) {		
				
				a--;
			
			// 왼쪽	
			}else if(direction ==2) {				
				
				b--;
				
			// 아래쪽	
			}else if(direction == 3) {	
			
				a++;				
			}	
			
			
			// 드래곤 커브가 범위밖을 벗어나지 않도록 
			if(a>=0 && a<=100 && b>=0 && b<=100) {
				map[a][b] = true;
			
			}			
		}		
	}
}

 

 

 

완성된 코드를 보면 각 상황의 방향값을 리스트에 넣는다.

 

방향값 
0 : 오른쪽 →

1 : 위 ↑

2 : 왼쪽 ←

3 : 아래 ↓

 

 

즉, 

4 2 1 3 의 경우에는

 

 

1) 차수가 0일 때는

 

리스트 : 1

 

2) 차수가 1일 때는

 

리스트 : 1,2

 

 

즉, 위방향은 1, 왼쪽 방향은 2

 

 

3) 차수가 2일 때는

 

리스트 : 1,2,3,2

 

 

 

위방향 1, 왼쪽 방향 2, 아래쪽 방향 3, 왼쪽방향 2

 

=> 그리고 코드에서 보면, 방향값을 구하는 메서드에서 (getDirection 메서드)

for 문 시작을 리스트의 제일 마지막 값부터 진행하는데,

이유가 있다.

 

차수가 1일 떄는 

위방향, 왼쪽방향이 순서대로 리스트[1,2] 에 들어가 있었다.

즉 바로 위의 그림에서 (위쪽)보라색, (왼쪽)초록색 그래프

그러면, 이제 차수가 2가 된 상황에서는 바로 초록색 그래프가 이어진다.(아래쪽)방향 그래프

떄문에, for문에서 리스트 마지막 값을 먼저 진행하는 것이다. 

 

 

 

 

 

참고 블로그 : 

백준15685번: 드래곤 커브 자바 해설 (삼성 SW 역량 테스트 기출 문제) (tistory.com)

백준15685번: 드래곤 커브 자바 해설 (삼성 SW 역량 테스트 기출 문제)