백준 15685 : 드래곤 커브

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

15685번: 드래곤 커브

[ 문제풀이 ]

전형적인 시뮬레이션 문제로써 이전 드래곤 커브의 상태를 어떻게 관리하여 다음 드래곤 커브의 상태를 만들 것인지가 가장 중요하다.

​다음 세대의 드래곤 커브는 끝 점을 기준으로 시계 방향으로 90도 회전한다고 하였다. 자세히 보면 끝점을 기준으로 지금까지 진행한 방향을 역순으로 90도 회전하면 다음 드래곤 커브를 만들어내는 것을 확인할 수 있다.

따라서 이전 드래곤 커브의 진행 방향과 끝점을 알고 있다면 다음 드래곤 커브의 상태를 쉽게 만들어낼 수 있다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N;
	static int[][] map;
	static int[][] dir = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());

		map = new int[101][101];

		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());

			//0세대 드래곤 커브 저장
			map[y][x] = 1;
			map[y + dir[d][0]][x + dir[d][1]] = 1;
			
			simulation(y + dir[d][0], x + dir[d][1], g, new StringBuilder(String.valueOf(d)));
		}

		bw.write(getAnswer() + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void simulation(int ey, int ex, int generation, StringBuilder beforeDir) {
		if (generation == 0) return;

		//기존 방향을 저장
		StringBuilder nextDir = new StringBuilder(beforeDir);

		//기존 방향을 역순으로 90도 회전하여 추가
		for (int i = beforeDir.length() - 1; i >= 0; --i) {
			int d = beforeDir.charAt(i) - '0';
			nextDir.append(String.valueOf((d + 1) % 4));
		}
		
		//기존 끝점을 추가된 방향만큼 이동
		for (int i = nextDir.length() / 2; i < nextDir.length(); ++i) {
			int d = nextDir.charAt(i) - '0';

			ey += dir[d][0];
			ex += dir[d][1];

			map[ey][ex] = 1;
		}

		simulation(ey, ex, generation - 1, nextDir);
	}

	public static int getAnswer() {
		int answer = 0;

		for (int i = 0; i < 100; ++i) {
			for (int j = 0; j < 100; ++j) {
				if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1 && map[i][j + 1] == 1) {
					answer++;
				}
			}
		}

		return answer;
	}
}