[JAVA] 백준 15685번 : 드래곤 커브(삼성 SW 역량 테스트 기출 문제)

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

15685번: 드래곤 커브

문제

구현 문제이다. 

 

해결 방안

map의 전체 크기는 101 x 101이 될 것이다. (전체 격자가 100x100 이므로)

1. 드래곤 커브의 갯수 N만큼 드래곤 커브의 정보들(x, y, d, g)을 받게 되는데

(drawDragonCurve() 함수 참고)
1.1. 각 드래곤 커브마다 g(세대)까지 map에 그려줘야한다.(드래곤 커브가 가지고 있는 꼭지점을 true로 만들어줘야한다. map[x][y] = true).
1.2. 이때 드래곤 커브를 그리는데 규칙이 있는데 다음 세대를 갈때 전 세대의 (가장 늦게 들어온 것부터 첫 번째 까지) 영향을 받는 것이다. 이때 반시계방향으로 방향이 바뀐다.
1.3. 따라서 드래곤 커브를 그리기 위해 해당 방향들을 list에 다 기억하고 있다가 주어진 x,y에 list 만큼 이어서 그려준다.
1.4. 드래곤 커브 갯수 N 만큼 드래곤 커브를 map에 그려준다. 

2. map에 드래곤 커브를 다 그리고 나면 1x1 정사각형의 네 꼭지점이 전부 true인 경우의 갯수를 찾으면 된다.

 

코드

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

// 드래곤 커브
// 세가지 속성(시작점, 시작방향, 세대)
// 이차원 좌표 평면 위에서 정의됨(x축은 동 방향 y축은 남 방향)

// 첫째 줄에 크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 갯수를 출력한다.
public class Main {
	
	// 전체 격자 100 x 100
	static int N; // 드래곤 커브 갯수 (1~20)
	static int x, y; // 드래곤 커브의 시작점(x,y) (0~100)
	static int d; // 시작 방향 (0~3) (0:동(x+)  1:북(y-)  2:서(x-)  3:남(y+))
	static int g; // 세대 (0~10)
	static boolean[][] map = new boolean[101][101]; // 드래곤 커브가 들어가면 해당 꼭지점(y, x)는 true
	
	static List<Integer> directions; // 선들의 방향을 저장할 List
	
	// (0:동(x+)  1:북(y-)  2:서(x-)  3:남(y+))
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, -1, 0, 1};
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		String str;
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());
			
			drawDragonCurve();
		}
		// === 입력 및 맵에 드래곤 커브 적용====
		
		int result = getSquareCnt();
		System.out.println(result);
	}
	
	// 드래곤 커브 그리기
	static void drawDragonCurve() {
		// 초기화
		directions = new ArrayList<>();
		directions.add(d); // 처음 방향 넣기

		// 드래곤 커브가 그려지는 선 방향 저장하기
		int dir;
		//g 세대 까지 반복
		while(g-- > 0) {
			// 전 세대의 영향을 받으며 stack과 같이 쌓여지므로 뒤에서부터 get
			for(int i=directions.size()-1; i>=0; i--) {
				dir = (directions.get(i)+1) % 4;
				directions.add(dir);
			}
		}
		
		// map에서 드래곤 커브가 지나는 꼭지점 그리기 
		int nx, ny;
		int cx = x;
		int cy = y;
		map[x][y] = true;
		for(int i=0; i<directions.size(); i++) {
			dir = directions.get(i);
			
			nx = cx + dx[dir];
			ny = cy + dy[dir];
			
			map[nx][ny] = true;
			
			// 계속 이어서 그려가는 것이므로 cx, cy를 바꿔줘야함
			cx = nx;
			cy = ny;
		}
	
	}
	
	//크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 갯수를 구하는 함수
	static int getSquareCnt() {
		int cnt = 0;
		
		for(int i=0; i<100; i++) { //y축
			for(int j=0; j<100; j++) { //x축
				if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1])
					cnt++;
			}
		}
		
		return cnt;
	}

}