15685번) 드래곤 커브

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

어렵다고 느껴졌네요.

특히 90도 회전하는 부분이요.

정답률 54%라는게 안믿겨질정도로...

공간 효율성 때문에 스택으로 처리하면 되겠지만,

배열을 사용한 시험용 코드이기 때문에 비효율적입니다.

2018년 5월 23일 - 다듬지 않은 코드 import java.util.Scanner; public class Q15685 { static int size = 101; static boolean[][] resultMap = new boolean[size][size]; static int finalGeneration; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); for (int i = 0; i < count; i++) { boolean[][] map = new boolean[size][size]; int x = sc.nextInt(); int y = sc.nextInt(); Point startPoint = new Point(y, x); Point endPoint = new Point(y, x);; int direction = sc.nextInt(); switch (direction) { case 0 : endPoint.x += 1; break; case 1 : endPoint.y -= 1; break; case 2 : endPoint.x -= 1; break; case 3 : endPoint.y += 1; break; } checkMap(resultMap, startPoint); checkMap(resultMap, endPoint); finalGeneration = sc.nextInt(); if (finalGeneration > 0) { checkMap(map, startPoint); checkMap(map, endPoint); // showMap(map, endPoint); nextGeneration(map, startPoint, endPoint, 1); } } int result = 0; for (int i = 0; i < size-1; i++) { for (int j = 0; j < size-1; j++) { if (resultMap[i][j] && resultMap[i][j+1] && resultMap[i+1][j] && resultMap[i+1][j+1]) { result += 1; } } } System.out.println(result); // showMap(resultMap, new Point(-1, -1)); } static void checkMap(boolean[][] map, Point point) { if (point.y >= 0 && point.x >= 0 && point.y < size && point.x < size) { map[point.y][point.x] = true; } } static void nextGeneration(boolean[][] map, Point startPoint, Point endPoint, int nowGeneration) { boolean[][] newMap = new boolean[size][size]; //기준 = endPoint for (int y = 0; y < size; y++) { for (int x = 0; x < size; x++) { if (map[y][x]) { newMap[y][x] = true; Point rotationPoint = getRotation(new Point(y,x), endPoint); if (rotationPoint.y >= 0 && rotationPoint.x >= 0) { checkMap(newMap, rotationPoint); checkMap(resultMap, rotationPoint); } } } } map = newMap; // showMap(map, getRotation(startPoint, endPoint)); if (nowGeneration == finalGeneration) { for (int y = 0; y < size; y++) { for (int x = 0; x < size; x++) { if (map[y][x]) { checkMap(resultMap, new Point(y,x)); } } } return; } else { nextGeneration(map, startPoint, getRotation(startPoint, endPoint), nowGeneration+1); } } static Point getRotation(Point point, Point endPoint) { int y = point.y; int x = point.x; Point rotationPoint = new Point(-1, -1); if (y < endPoint.y && x == endPoint.x){ //1 rotationPoint.y = endPoint.y; rotationPoint.x = endPoint.x + (endPoint.y - y); } else if (y < endPoint.y && x > endPoint.x){ //2 rotationPoint.y = endPoint.y + (x - endPoint.x); rotationPoint.x = endPoint.x + (endPoint.y - y); } else if (y == endPoint.y && x > endPoint.x ){ //3 rotationPoint.y = endPoint.y + (x - endPoint.x); rotationPoint.x = endPoint.x; } else if (y > endPoint.y && x > endPoint.x){ //4 rotationPoint.y = endPoint.y + (x - endPoint.x); rotationPoint.x = endPoint.x - (y - endPoint.y); } else if (y > endPoint.y && x == endPoint.x ){ //5 rotationPoint.y = endPoint.y; rotationPoint.x = endPoint.x - (y - endPoint.y); } else if (y > endPoint.y && x < endPoint.x){ //6 rotationPoint.y = endPoint.y - (endPoint.x - x); rotationPoint.x = endPoint.x - (y - endPoint.y); } else if (y == endPoint.y && x < endPoint.x){ //7 rotationPoint.y = endPoint.y - (endPoint.x - x); rotationPoint.x = endPoint.x; } else if (y < endPoint.y && x < endPoint.x){ //8 rotationPoint.y = endPoint.y - (endPoint.x - x); rotationPoint.x = endPoint.x + (endPoint.y - y); } return rotationPoint; } static void showMap(boolean[][] map, Point point) { System.out.println((point.x+1) + ", " + (point.y+1)); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (map[i][j]) { System.out.print("■ "); } else { System.out.print("□ "); } } System.out.println(); } System.out.println(); } } class Point { int y, x; public Point(int y, int x) { this.y = y; this.x = x; } }