15685 번 문제 풀이

using Java 11

15685 문제 보기

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;