[BOJ] 백준 15685 - 드래곤 커브
15685 번 문제 풀이
using Java 11
package BOJ;
import java.util.*;
import java.io.*;
public class boj15685 {
public static int[] dx = {1, 0, -1, 0};
public static int[] dy = {0, -1, 0, 1};
public static int N;
public static int count = 0;
public static int[][] map = new int[101][101];
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
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());
makeCurve(x, y, d, g);
}
System.out.println(countSquare());
}
public static boolean isValid(int x, int y) {
if(x < 0 || y < 0 || x > 100 || y > 100) {
return false;
}
return true;
}
public static void makeCurve(int x, int y, int d, int g) {
LinkedList<Integer> direction = new LinkedList<>();
direction.add(d);
map[y][x] = 1;
x = x + dx[d];
y = y + dy[d];
map[y][x] = 1;
while(g-- > 0) {
for(int i = direction.size()-1; i >= 0; i--) {
int nDir = (direction.get(i)+1) % 4 ;
int nx = x + dx[nDir];
int ny = y + dy[nDir];
if(isValid(nx, ny)) {
map[ny][nx] = 1;
direction.add(nDir);
x = nx;
y = ny;
}
}
}
}
public static int countSquare() {
for(int i = 0; i < 100; i++) {
for(int j = 0; j < 100; j++) {
if(map[i][j] == 0) continue;
else if(map[i][j] == 1 && map[i+1][j] == 1 &&
map[i][j+1] == 1 && map[i+1][j+1] == 1) count++;
}
}
return count;
}
}
📍 규칙찾기
0세대 커브를 제외하고는 각 커브의 방향을 역순으로 반시계 90도 회전 시키면 된다.
주어진 예제에서는
0
0 1
0 1 2(1이 90도 회전) 1(0이 90도 회전) 이렇게 진행된다.
즉, 방향에 해당하는 정수 값을 list에 넣고 뒤에서 부터 탐색하여 90도 회전 시켜주면 된다는 것이다.
for(int i = direction.size()-1; i >= 0; i--) { int nDir = (direction.get(i)+1) % 4 ; int nx = x + dx[nDir]; int ny = y + dy[nDir]; if(isValid(nx, ny)) { map[ny][nx] = 1; direction.add(nDir); x = nx; y = ny; } }
📍 주의할 점
0세대에 대해서는 먼저 수행해서 x, y 값이 끝점으로 업데이트 되어야 한다. 그래야 방향을 넣고 반복문을 돌렸을 때 겹치지 않고 수행된다.
direction.add(d); map[y][x] = 1; x = x + dx[d]; y = y + dy[d]; map[y][x] = 1;
Author And Source
이 문제에 관하여([BOJ] 백준 15685 - 드래곤 커브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@since1909/BOJ15685저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)