[BaekJoon] 15685 드래곤 커브 (Java)

1.  문제 링크

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

2.  문제

요약

• 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의됩니다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향입니다.
  1. 시작 점
  2. 시작 방향
  3. 세대
• 0세대 드래곤 커브는 길이가 1인 선분입니다. 시작 방향은 오른쪽인 0세대 드래곤 커브입니다.
• 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것입니다.
  • 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미합니다.
• K세대 드래곤 커브는 K - 1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝점에 붙인 것입니다.
• 크기가 100 x 100 격자 위에 드래곤 커브가 N개 있는데, 이때 크기가 1 x 1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 20보다 작거나 같은 드래곤 커브의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어집니다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있고 x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대를 의미합니다.
  • 0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10
  • 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않고, 드래곤 커브는 서로 겹칠 수 있습니다.
  • 방향은 0, 1, 2, 3 중 하나이고, 다음을 의미합니다.
    • 0: x좌표가 증가하는 방향 (→)
      • 1: y좌표가 감소하는 방향 (↑)
      • 2: x좌표가 감소하는 방향 (←)
      • 3: y좌표가 증가하는 방향 (↓)
• 출력: 첫 번째 줄에 크기가 1 x 1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력합니다.

3.  소스코드

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

public class Main {
	static Reader scanner = new Reader();
	static final int MAX_SIZE = 101;
	static final int[] ROTATE_DIR = {1, 2, 3, 0};
	static final int[][] MOVE_PER_DIR = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
	static int[] startInfo;
	static boolean[][] isCurve;
	static void input() {
		startInfo = new int[4];
		startInfo[1] = scanner.nextInt(); // x좌표(col 좌표)
		startInfo[0] = scanner.nextInt(); // y좌표(row 좌표)
		startInfo[2] = scanner.nextInt(); // 방향
		startInfo[3] = scanner.nextInt(); // 세대
	}
	
	static void solution() {
		ArrayList<Curve> curveList = new ArrayList<Curve>();
		init(curveList);
		if(startInfo[3] == 0) return;
		makeDragonCurve(curveList);
	}
	
	static void init(ArrayList<Curve> curveList) {
		curveList.add(new Curve(new int[] {startInfo[0], startInfo[1]},
				new int[] {startInfo[0] + MOVE_PER_DIR[startInfo[2]][0], startInfo[1] + MOVE_PER_DIR[startInfo[2]][1]}, startInfo[2]));
		isCurve[curveList.get(0).start[0]][curveList.get(0).start[1]] = true;
		isCurve[curveList.get(0).end[0]][curveList.get(0).end[1]] = true;
	}
	
	static void makeDragonCurve(ArrayList<Curve> curveList) {
		for(; startInfo[3] > 0; startInfo[3]--) makeNthDragonCurve(curveList);
	}
	
	static void makeNthDragonCurve(ArrayList<Curve> curveList) {
		ArrayList<Curve> tempList = new ArrayList<Curve>();
		for(int index = curveList.size() - 1; index >= 0; index--) {
			int[] start = new int[2];
			// 커브의 시작 위치 설정
			if(tempList.size() == 0) {
				start[0] = curveList.get(curveList.size() - 1).end[0];
				start[1] = curveList.get(curveList.size() - 1).end[1];
			} else {
				start[0] = tempList.get(tempList.size() - 1).end[0];
				start[1] = tempList.get(tempList.size() - 1).end[1];
			}
			// 변경된 방향 설정
			int changedDir = ROTATE_DIR[curveList.get(index).direction];
			// tempList에 변경된 커브 넣기
			tempList.add(new Curve(new int[] {start[0], start[1]},
					new int[] {start[0] + MOVE_PER_DIR[changedDir][0], start[1] + MOVE_PER_DIR[changedDir][1]}, changedDir));
			// 커브로 설정된 곳 설정
			isCurve[start[0]][start[1]] = true;
			isCurve[tempList.get(tempList.size() - 1).end[0]][tempList.get(tempList.size() - 1).end[1]] = true;
		}
		// N세대의 드래곤 커브에 있는 커브들을 갱신
		curveList.addAll(tempList);
	}
	
	static int getSquareNum() {
		int result = 0;
		for(int row = 0; row < MAX_SIZE - 1; row++) {
			for(int col = 0; col < MAX_SIZE - 1; col++) {
				if(isCurve[row][col] && isCurve[row][col + 1] && isCurve[row + 1][col] && isCurve[row + 1][col + 1])
					result++;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		int n = scanner.nextInt();
		isCurve = new boolean[MAX_SIZE][MAX_SIZE];
		while(n-- > 0) {
			input();
			solution();
		}
		System.out.println(getSquareNum());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Curve {
		int[] start, end;
		int direction;
		public Curve(int[] start, int[] end, int direction) {
			this.start = start;
			this.end = end;
			this.direction = direction;
		}
	}
}

4.  접근

• 각 길에 대해서 문제에서 주어진 조건들을 하나씩 확인해보고 모든 조건을 만족하는 길의 개수를 구하는 문제입니다.
• 각 길에서 경사로를 겹쳐서 놓을 수 없기 때문에 경사로를 놓았는지를 나타내는 slopeWay라는 boolean 타입의 2차원 배열을 만들고 경사로가 필요할 때 이 배열에 경사로를 표시하고 경사로가 겹치는지를 확인합니다.
• 조건 확인은 행에서의 길과 열에서의 길이 같은 방식이기 때문에 행에서의 길에 대해서만 확인해보겠습니다.

checkRows 함수

static boolean checkRows(int row) {
	int num = map[row][0];
	for(int col = 1; col < N; col++) {
		if(num == map[row][col]) continue;
		if(num > map[row][col]) { // 높이가 낮아졌을 때
			if(map[row][col] < num - 1) return false;
			if(col + L - 1 >= N) return false;
			num = map[row][col];
			for(int col2 = col; col2 <= col + L - 1; col2++) {
				if(slopeWay[row][col2]) return false;
				slopeWay[row][col2] = true;
				if(num != map[row][col2]) {
					return false;
				}
			}
		} else if(num < map[row][col]) { // 높이가 높아졌을 때
			if(map[row][col] > num + 1) return false;
			if(col - L < 0) return false;
			num = map[row][col - 1];
			for(int col2 = col - L; col2 < col; col2++) {
				if(slopeWay[row][col2]) return false;
				slopeWay[row][col2] = true;
				if(num != map[row][col2]) {
					return false;
				}
			}
			num = map[row][col];
		}
	}
	return true;
}

• 이 함수는 행에서의 길에서 지나갈 수 있는 길인지 확인하는 함수입니다.
• 이 함수를 실행시키기 이전에 모든 칸이 같은 높이인지 먼저 확인하고 그렇다면 이미 지나갈 수 있는 길임을 확인했기 때문에 지나갈 수 있는 길의 개수를 하나 증가시켜주고 다음 길을 확인하고 그렇지 않을 때에 이 함수를 호출해 지나갈 수 있는 길인지 확인합니다.
• 왼쪽부터 오른쪽으로, 즉 열의 index가 0일 때부터 N - 1일 때까지 확인하는데, 이 때 높이가 높아지는 경우와 낮아지는 경우, 높이가 같은 경우가 있습니다.
• 높이가 같은 경우는 지나갈 수 있기 때문에 다음 열을 확인합니다.
• 높아지는 경우와 낮아지는 경우는 같은 방식이기 때문에 낮아지는 경우에 대해서만 살펴보겠습니다.
• 만약 높이가 낮아졌다면 높이가 1보다 더 낮아졌는지 확인하고 그렇다면 경사로를 통해서도 이동을 할 수 없기 때문에 지나갈 수 없는 길임을 반환합니다.
• 또한, 높이가 낮아진 곳부터 L만큼 이동한 곳이 길을 벗어난다면 경사로를 놓을 수 없기 때문에 이 또한 지나갈 수 없는 길임을 반환합니다.
• 위 두 경우를 만족했다면 높이가 낮아진 곳부터 L만큼 이동한 곳까지 각 위치를 살펴보면서 경사로를 놓을 수 있는지 확인합니다.
  • 만약 이미 경사로가 놓여진 위치가 있다면 해당 위치에는 경사로를 설치할 수 없기 때문에 지나갈 수 없는 길임을 반환합니다.
  • 만약 그렇지 않다면 그 위치에는 경사로를 세워놓기 위해 해당 위치의 slopeWay 값을 true로 변경합니다.
  • 만약 낮아진 높이와 높이가 다른 칸이 존재한다면 경사로는 낮은 지점의 높이가 같은 곳에만 놓을 수 있다는 조건에 위배되므로 지나갈 수 없는 길임을 반환합니다.
• 위 조건들을 모두 만족했다면 해당 길은 지나갈 수 있는 길이기 때문에 지나갈 수 있는 길임을 반환합니다.