[JAVA] BOJ(백준) - 드래곤 커브 - 15685

문제내용

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

15685번: 드래곤 커브

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 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×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

---

문제 접근 방법

처음에 접근했던 생각이 입력받은 값에 있는 n세대 만큼 돌면서 세대가 지날 때마다 배열에 그려져있는 커브들을 누적해서 시계방향으로 한번에 그리는것을 생각했다. 이렇게 삽질을 1시간정도 했다,,,ㅎㅎ

 

로직은 한세대 채우고, 그 다음 세대 채우고,, 하는게 아니라 드래곤 커브의 방향을 전부 구한뒤에 한번에 다 그리는 로직이다. 이를 좀 자세히 말해보자면 아래와 같다.

 

1. 규칙찾기.

먼저 방향을 계산하기 위해선 dx, dy배열을 시계방향으로 해놓는다.(이렇게 해야 계산이 편하고, 이에 대한 문제는 https://record-developer.tistory.com/99 해당 문제를 풀어보면서 익히자.)

이후 문제 내용에 나와있는 드래곤 커브의 방향을 잘보면 규칙이나온다.

 

문제에서 방향 -> 오른쪽:0 , 위쪽:1 , 왼쪽:2, 아래쪽:3

0세대 방향 : 0

1세대 방향 : 0 1 

2세대 방향 : 0 1 2 1

3세대 방향 : 0 1 2 1 2 3 2 1

 

이에 대한 규칙을 보면 첫번째로 세대가 지날수록 "방향의 개수 = 이전세대*2" 가된다.

두번째로 이전세대의 방향들은 현재세대의 앞부분의 방향 + 뒤집은 이전세대 방향들+1 이다.

즉, 2세대의 (1 0 2 1) 에서 +1을 한값이 3세대의 뒷부분 (2 3 2 1) 이된다.

 

참고로 문제에서 x,y는 반대로 돼있기 때문에

int[] dx={1,0,-1,0};
int[] dy={0,-1,0,1};

로 해줘야 한다.

 

2. 방향 구하기.

규칙을 알았으니 이제 방향을 구하면된다.

방향을 구하는건 입력 받은 g값(세대) 만큼 반복하면서 리스트에 방향을 넣어준다. 이때, 다음세대 방향은 리스트의 뒷부분부터 뽑아내면서+1 한 값을 추가해주면 된다.

 

3. 커브 그리고, 꼭지점이 다 채워진 사각형 개수 세기.

커브를 그리는건 쉽다. 리스트에 있는 방향들을 첫부분 부터 빼면서 현재 인덱스인 x,y를 방향에 따라 변화 시켜주면된다. 이때 변화된 x,y를 그대로 두고 다음 방향으로 x,y를 갱신해야한다는 점을 주의하자. 또한, 문제에서 이미 드래곤커브는 배열밖을 나갈일이 없다고 했으므로 다음 인덱스가 배열 밖으로 나가는지 안나가는지 검사할 필요가 없다.

 

이후 배열에 드래곤커브를 그리게 되면 배열의 좌상단~우하단까지 검사한다. 그리고 (현재좌표, 현재좌표+우, 현재좌표+우하, 현재좌표+하)에 꼭지점이 다 채워져 있다면 카운트를 +1하면된다.

 

이 과정을 거쳐서 개수를 전부 구하고 출력해주면 된다.

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static private int n;
	//0<=x,y<=100 이라서 크기를 101로 해줘야됨.
	static private final boolean[][] map = new boolean[101][101];
	static private List<Integer> dirList;
	//0:오른쪽 , 1:위쪽, 2:왼쪽, 3:아래쪽
	//하지만 문제에서 x,y의 좌표가 반대라서 아래 dx,dy도 반대로 넣어줘야 답이나옴.
	static private int[] dx={1,0,-1,0};
	static private int[] dy={0,-1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++) {
			StringTokenizer 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());
			
			dirList = new LinkedList<Integer>();
			addDirAll(d,g);//각 세대마다 방향을 전부 넣기.
			drawDragon(x,y);//시작점부터 모든뱡향으로 좌표 하나씩 방문처리.
		}
		
		int ans = checkSquare();
		System.out.println(ans);
		
	}
	
	//이전세대*2 = 다음세대 방향 수
	//즉, 3세대는 총 8번의 방향정보가 나옴.
	public static void addDirAll(int d, int g) {
		dirList.add(d);//0세대일때 방향 추가
		
		for(int i=1; i<=g; i++) {
			for(int j=dirList.size()-1; j>=0; j--) {
				dirList.add((dirList.get(j)+1)%4);
			}
		}
		
	}
	
	//꼭지점 그리기.
	//주의: 문제에서 x,y좌표가 거꾸로 돼있음.
	public static void drawDragon(int x, int y) {
		map[x][y] = true;//초기위치 그리기.
		
		int nx=x , ny=y;
		for(int i=0; i<dirList.size(); i++) {
			int d = dirList.get(i);
			
			nx += dx[d];
			ny += dy[d];
			
			map[nx][ny] = true;
		}
	}
	
	//꼭지점이 4개 채워진 사각형 개수 카운트
	public static int checkSquare() {
		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++;
			}
		}
		
		return cnt;
	}
}​

---

마무리

오랜만에 풀었던 알고리즘에 대한 글을 쓴다. 문제는 거의 매일 한문제 이상씩 풀고 있는데 프로젝트+자소서+면접이 겹치다보니,, 포스팅을 할 시간이 별로 없었다. 그래도 이제 시간이 좀 생겨서 다행이다..! 다행인가,,??

아무튼 이번 문제는 삼성코테 문제로 그냥 구현문제인데 이런류의(시뮬레이션) 문제를 안풀어봤다면 오래걸릴 문제이다. 연습하자..!