백준_15685_드래곤 커브

문제 링크

조건

• x : 커브 시작 열의 위치
• y : 커브 시작 행의 위치
• d : 커브 방향 ( 0 <= d <= 3)
• g : 커브 세대 수

 

접근 방법

• curve : 0 ~ 10 세대까지의 커브 정보를 미리 저장해 둠(0번 방향 기준으로)
• point : N개의 커브를 조건대로 찍어보며 100 X 100 크기의 맵 범위 안에 드는 경우만 저장
• 이후에 map[][] 지도에 point에 저장된 정보를 모두 찍고 정사각형 개수 체크

 

솔루션

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

public class Main {
	static int N;
	static boolean[][] map;
	static List<int[]> curve;//0방향 기준 10세대까지 저장
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine().trim());
		
		curve = new ArrayList<int[]>();
		curve.add(new int[] {0,0});//0세대
		curve.add(new int[] {0,1});//0세대
		//10세대 미리 저장
		int r,c,nr = 0,nc = 0,a,b;
		for(int i = 0; i < 10; i++) {
			int[] base = curve.get((int) Math.pow(2, i)); 
		
			for(int j = curve.size()-2; j > -1; j--) {
				int[] cur = curve.get(j);
				r = cur[0];
				c = cur[1];
				//cur 90도 회전에서 point뒤에 넣어줌
				a = r - base[0];
				b = c - base[1];
				
				nr = base[0] + b;
				nc = base[1] - a;
				curve.add(new int[] {nr,nc});
			}
		}
		
		int baseR,baseC,d,g;
		List<int[]> point = new ArrayList<int[]>();
		while(N-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
			baseC = Integer.parseInt(st.nextToken());
			baseR = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());//방향
			g = Integer.parseInt(st.nextToken());//세대
			
			int size = (int) Math.pow(2, g);
			for(int i = 0; i <= size; i++) {//curve의 0~size-1번째 까지 커브 point에 더해줌 
				int[] cur = curve.get(i);
				
				a = cur[0];//기준점에서 떨어진 행 크기
				b = cur[1];//기준점에서 떨어진 열 크기
				switch (d) {
				case 0: //0도회전
					nr = baseR + a;
					nc = baseC + b;
					break;
				case 3: //90도회전
					nr = baseR + b;
					nc = baseC - a;
					break;
				case 2: //180도회전
					nr = baseR - a;
					nc = baseC - b;
					break;
				case 1: //270도회전
					nr = baseR - b;
					nc = baseC + a;
					break;
				}
				
				///////////// 맵 범위 0 <= r,c <= 100 //////////////
				if(nr < 0 || nr > 100 || nc < 0 || nc > 100) continue;
				point.add(new int[] {nr,nc});
			}
			
		}
		map = new boolean[101][101];
		for(int[] cur : point) {
			map[cur[0]][cur[1]] = true;
		}
		
		int ans = 0;
		for(int i = 0; i < 100; i++) {
			for(int j = 0; j < 100; j++) {
				if(!map[i][j]) continue;
				
				if(map[i][j+1] && map[i+1][j] && map[i+1][j+1]) ans++;
			}
		}
		System.out.println(ans);
	}
}

 

리뷰

• 90도 회전 좌표를 확인하는 부분이 헷갈려서 시간 오래 걸림
  • (r, c) 좌표를 기준으로 (r+a, c+b) 좌표를 시계방향 90도 회전 시 (r+b, c-a)가 됨!