백준 15685 드래곤 커브 - 삼성 SW 역량 테스트 기출

백준 15685 드래곤 커브 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

15685번: 드래곤 커브

 

2. 문제 해결에 대한 아이디어

1. 이 문제는 드래곤 커브가 어떤 규칙을 갖는지 파악하는게 중요했다.

2. 각 방향은 숫자와 매핑되어 있다 0 : → / 1: ↑ / 2 : ←  / 3 : ↓

3. 드래곤 커브가 세대를 거듭하면서 그려지는 예시를 보면 아래의 규칙을 찾을 수 있다.

   . 0 세대 : →

   . 1 세대 : → ↑

   . 2 세대 : → ↑ ← ↑

   . 3 세대 : → ↑ ← ↑←↓←↑

   . n + 1 세대는 n 세대의 최근 이동 방향부터 처음 이동 방향 순으로 각 방향의 반시계 90도 회전으로 움직였다.

4. 따라서 각 이동 방향을 기록하여 새로운 세대를 그릴 때 기록된 방향을 반시계 90도 회전하여 이동했다.

   . 0 세대 : → 

      . 0 세대의 이동 방향 기록 {→}

   . 1 세대 : → ↑

      . 끝에 있는 방향부터 90도 회전하여 그리기 [ → => ↑]

      . 1 세대의 이동 방향 기록 {→, ↑}

   . 2 세대 : → ↑ ← ↑

      . 끝에 있는 방향부터 90도 회전하여 그리기 [↑ => ←][ → => ↑]

      . 2 세대의 이동 방향 기록 {→, ↑, ←, ↑}

   . 3 세대 : → ↑ ← ↑ ← ↓ ← ↑

      . 끝에 있는 방향부터 90도 회전하여 그리기 [↑ => ←][ ← => ↓][ ↑ => ←][ → => ↑]

      . 3 세대의 이동 방향 기록 {→, ↑, ←, ↑, ←, ↓, ←, ↑}

5. 이 규칙을 찾아냈다면 구현은 어렵지 않다.

6. 기록할 때 움직였던 방향을 기록해도 되고, 반시계 회전한 방향을 기록해도 되겠다. (난 전자)

7. 정사각형을 만드는지의 여부

   . 현 위치가 드래곤 커브의 일부일 때,  → ↓↘ 가 드래곤 커브인지 확인

3. 코드

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

public class Main {

	static int[] dirY = { 0, -1, 0, 1 };
	static int[] dirX = { 1, 0, -1, 0 };
	static int N; // 드래곤 커브의 갯수
	static int[][] board = new int[101][101];
	static int[][] rectangle = { { 1, 1 }, { 1, 1 } };
	static ArrayList<Integer> cmds;
	static int answer = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			int x = Integer.parseInt(line[0]);
			int y = Integer.parseInt(line[1]);
			int d = Integer.parseInt(line[2]);
			int g = Integer.parseInt(line[3]);

			cmds = new ArrayList<>();
			board[y][x] = 1;

			while (g >= 0) {
				if (cmds.isEmpty()) {
					y = y + dirY[d];
					x = x + dirX[d];
					board[y][x] = 1;
					cmds.add((d + 1) % 4);
				} else {
					ArrayList<Integer> temp = new ArrayList<>();
					for (int c = cmds.size() - 1; c >= 0; c--) {
						int dd = cmds.get(c);
						y = y + dirY[dd];
						x = x + dirX[dd];
						board[y][x] = 1;
						temp.add(dd);
					}

					for (int j = 0; j < temp.size(); j++) {
						cmds.add((temp.get(j) + 1) % 4);
					}
				}
				--g;
			}
		}
		count();
		System.out.println(answer);
	}

	private static void count() {
		// 2 * 2 부분 배열이 모두 1인지 판단함
		// 현 위치에서 +1행 1열을 확인하므로 인덱스의 범위는 100
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				if (board[i][j] == 1) {
					if (board[i + 1][j] == 1 && board[i][j + 1] == 1 && board[i + 1][j + 1] == 1) {
						++answer;
					}
				}
			}
		}
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 맞딱뜨리면 어떻게 구현해야할지 난감하지만 규칙을 찾아내면 매우 간단하다.

2. 처음에 반시계 방향임을 생각 못 해서 방향을 반대로 뒤집고 시계 방향으로 돌렸었다.

   . → (반대로 뒤집기) ← (시계 방향으로 회전)↑