* 핵심 개념
풀어왔던 삼성 기출문제중에서 BFS, DFS 개념이 필요없는 문제
1. 규칙
이전 방향을 Stack에 저장해서(필자는 String에 붙이는 방식 사용) 뒤에서부터 가져다 쓰는 규칙을 찾으면 쉽게 풀림
ex) 1세대를 움직이는데, 이전 이동한 방향이 3, 0 이라면 다음 이동은 1, 0((3+1)%4)이 된다.
2. 0세대
n번째 세대는 2^n번 움직이지만 0세대는 예외로 그냥 움직인다.
이때는 움직임을 저장하지 않고 현재 x,y 좌표만 변경하면 된다.
* 문제
문제
드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.
- 시작 점
- 시작 방향
- 세대
0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.
... 생략
즉, 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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.
* 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | import java.io.*; import java.util.*; public class Main { public static StringTokenizer stk; public static StringBuilder sb = new StringBuilder(); public static int[] dx = {1, 0, -1, 0}; public static int[] dy = {0, -1, 0, 1}; public static boolean[][] visited = new boolean[101][101]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); for (int i = 1; i <= t; i++) { stk = new StringTokenizer(br.readLine()); int x = Integer.parseInt(stk.nextToken()); int y = Integer.parseInt(stk.nextToken()); int d = Integer.parseInt(stk.nextToken()); int g = Integer.parseInt(stk.nextToken()); String s = String.valueOf(d); visited[x][y] = true; for (int j = 0; j <= g; j++) { //1세대마다 2의 제곱으로 늘어남 if (j != 0 && s.length() >= Math.pow(2, j)) continue; for (int k = s.length() - 1; k >= 0; k--) { int nd; if (j == 0) nd = s.charAt(k) - '0'; else nd = (s.charAt(k) - '0' + 1) % 4; int nx = x + dx[nd]; int ny = y + dy[nd]; visited[nx][ny] = true; x = nx; y = ny; if (j != 0) s += nd; } } } System.out.println(check()); } public static int check() { int ans = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { if (visited[i][j] && visited[i + 1][j] && visited[i][j + 1] && visited[i + 1][j + 1]) ans++; } } return ans; } } | cs |
'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글
| [Algorithm] 백준/17136 :: 색종이 붙이기 (1) | 2019.04.13 |
|---|---|
| [Algorithm] 백준/17135 :: 캐슬 디펜스 (0) | 2019.04.06 |
| [Algorithm] 백준/15686 :: 치킨 배달 (1) | 2019.03.27 |
| [Algorithm] 백준/16234 :: 인구 이동 (0) | 2019.03.24 |