https://www.acmicpc.net/problem/15685
15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커�
www.acmicpc.net
문제
구현 문제이다.
해결 방안
map의 전체 크기는 101 x 101이 될 것이다. (전체 격자가 100x100 이므로)
1. 드래곤 커브의 갯수 N만큼 드래곤 커브의 정보들(x, y, d, g)을 받게 되는데
(drawDragonCurve() 함수 참고)
1.1. 각 드래곤 커브마다 g(세대)까지 map에 그려줘야한다.(드래곤 커브가 가지고 있는 꼭지점을 true로 만들어줘야한다. map[x][y] = true).
1.2. 이때 드래곤 커브를 그리는데 규칙이 있는데 다음 세대를 갈때 전 세대의 (가장 늦게 들어온 것부터 첫 번째 까지) 영향을 받는 것이다. 이때 반시계방향으로 방향이 바뀐다.
1.3. 따라서 드래곤 커브를 그리기 위해 해당 방향들을 list에 다 기억하고 있다가 주어진 x,y에 list 만큼 이어서 그려준다.
1.4. 드래곤 커브 갯수 N 만큼 드래곤 커브를 map에 그려준다.
2. map에 드래곤 커브를 다 그리고 나면 1x1 정사각형의 네 꼭지점이 전부 true인 경우의 갯수를 찾으면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 드래곤 커브
// 세가지 속성(시작점, 시작방향, 세대)
// 이차원 좌표 평면 위에서 정의됨(x축은 동 방향 y축은 남 방향)
// 첫째 줄에 크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 갯수를 출력한다.
public class Main {
// 전체 격자 100 x 100
static int N; // 드래곤 커브 갯수 (1~20)
static int x, y; // 드래곤 커브의 시작점(x,y) (0~100)
static int d; // 시작 방향 (0~3) (0:동(x+) 1:북(y-) 2:서(x-) 3:남(y+))
static int g; // 세대 (0~10)
static boolean[][] map = new boolean[101][101]; // 드래곤 커브가 들어가면 해당 꼭지점(y, x)는 true
static List<Integer> directions; // 선들의 방향을 저장할 List
// (0:동(x+) 1:북(y-) 2:서(x-) 3:남(y+))
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, -1, 0, 1};
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
String str;
StringTokenizer st;
for(int i=0; i<N; i++) {
str = br.readLine();
st = new StringTokenizer(str, " ");
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
drawDragonCurve();
}
// === 입력 및 맵에 드래곤 커브 적용====
int result = getSquareCnt();
System.out.println(result);
}
// 드래곤 커브 그리기
static void drawDragonCurve() {
// 초기화
directions = new ArrayList<>();
directions.add(d); // 처음 방향 넣기
// 드래곤 커브가 그려지는 선 방향 저장하기
int dir;
//g 세대 까지 반복
while(g-- > 0) {
// 전 세대의 영향을 받으며 stack과 같이 쌓여지므로 뒤에서부터 get
for(int i=directions.size()-1; i>=0; i--) {
dir = (directions.get(i)+1) % 4;
directions.add(dir);
}
}
// map에서 드래곤 커브가 지나는 꼭지점 그리기
int nx, ny;
int cx = x;
int cy = y;
map[x][y] = true;
for(int i=0; i<directions.size(); i++) {
dir = directions.get(i);
nx = cx + dx[dir];
ny = cy + dy[dir];
map[nx][ny] = true;
// 계속 이어서 그려가는 것이므로 cx, cy를 바꿔줘야함
cx = nx;
cy = ny;
}
}
//크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 갯수를 구하는 함수
static int getSquareCnt() {
int cnt = 0;
for(int i=0; i<100; i++) { //y축
for(int j=0; j<100; j++) { //x축
if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1])
cnt++;
}
}
return cnt;
}
}
'Old > Algorithms' 카테고리의 다른 글
| [JAVA] 프로그래머스 : 124 나라의 숫자 (0) | 2020.08.26 |
|---|---|
| [JAVA] 백준 15686번 : 치킨 배달(삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.25 |
| [JAVA] 백준 15683번 : 감시(삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.23 |
| [JAVA] 백준 14891번 : 톱니바퀴 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.22 |
| [JAVA] 백준 14890번 : 경사로 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.19 |
