[백준] 15685 드래곤 커브 - Implementation / Java

• 문제 링크

15685번: 드래곤 커브

 

• 풀이 과정

입력받은 선분의 방향(dir) 을 List 에 추가한다.

리스트의 마지막 인덱스부터, 세대(gen) 수 만큼 반시계 방향으로 90도 회전한 드래곤 커브를 리스트에 추가하여

세대 별 드래곤 커브의 형태를 구현한다.

 

좌표 상 해당 드래곤 커브의 꼭짓점의 위치를 boolean 형태 2차원 배열에 표시하고,

해당 배열을 모두 탐색해 크기가 1x1인 정사각형의 네 꼭짓점이 true 인 개수를 반환한다.

이때 런타임 에러를 방지하기 위하여 배열의 크기는 101x101 로 설정한다.

• 풀이 코드

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

public class Main {

	static boolean[][] map = new boolean[101][101];
	static int[] dy = { 0, -1, 0, 1 };
	static int[] dx = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			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());

			setCurve(y, x, d, g);
		}

		int cnt = 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])
					cnt++;
			}
		}

		bw.write(cnt + "\n");
		bw.flush();
	}

	private static void setCurve(int y, int x, int dir, int gen) {
		List<Integer> list = new ArrayList<>();
		list.add(dir);

		for (int i = 0; i < gen; i++) {
			for (int j = list.size() - 1; j >= 0; j--)
				list.add((list.get(j) + 1) % 4);
		}

		map[y][x] = true;
		for (Integer i : list) {
			y += dy[i];
			x += dx[i];
			map[y][x] = true;
		}
	}

}