백준 15685 - 드래곤 커브

Java

15685 번 - 드래곤 커브

문제

주어진 N개의 드래곤 커브를 수행하여, 100x100 격자 내의 모든 정사각형의 수를 구한다.

첫째 줄에 드래곤 커브의 개수 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,2,4,8,16…] 순으로 늘어난다.
세대가 증가 할 때마다, 이전까지의 드래곤 커브의 방향을 역으로 탐색하여 그 방향을 1씩 증가한 것이 추가된다.
예를 들어, 현재 드래곤 커브가 [0,1,2,3]이라면, 다음 세대는 [0,1,2,3, 0,3,2,1]이 된다.
총 n개의 드래곤 커브를 실행하여, 각 세대만큼 그래프 방향을 List에 넣는다.
새로운 방향을 찾으면, 그에 따른 끝점에서 방향에 따라 점을 이동하여 방문 여부를 체크한다.

정사각형의 개수를 찾기

0,0에서 99,99까지 점을 탐색한다.
각 점에서 (k,k+1), (k+1,k), (k+1,k+1) 점을 탐색하여 만약 4점이 다 true이면 해당 네모는 정사각형이므로, 이러한 점의 개수를 센다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[][] map;
	static int[] dy = {0, -1, 0, 1};
	static int[] dx = {1, 0, -1, 0};	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	map = new int[101][101];
    	int y, x, d, g, size;

		// 각각의 드래곤 커브를 시작한다
    	end : while(n-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		x = stoi(stk.nextToken());
    		y = stoi(stk.nextToken());
    		d = stoi(stk.nextToken());
    		g = stoi(stk.nextToken());
    		List<Integer> dir = new ArrayList<Integer>();
    		// 0세대 입력
    		map[y][x] = 1;
    		dir.add(d);
    		int ny = y + dy[d];
    		int nx = x + dx[d];
    		// 0세대가 격자를 벗어날 시
    		if(!isIn(ny,nx,100)) {
				continue end;
			}

    		map[ny][nx] = 1;
    		int curD;
    		for(int i = 0; i < g; i++) {	// 세대 시작
    			size = dir.size();
    			for(int j = size - 1; j >= 0; j--) {
    				curD = (dir.get(j) + 1) % 4;	// 현재까지의 세대에서 역으로 탐색하여 1씩 증가한 것이 새로운 세대의 그래프 방향이다.
    				dir.add(curD);
    				ny = ny + dy[curD];				// 방향대로 해당하는 점을 방문처리한다.
    				nx = nx + dx[curD];
    				if(!isIn(ny,nx,100)) {
    					continue end;
    				}
    				map[ny][nx] = 1;
    			}
    		}
    	}
    	
		// 정사각형의 개수를 세는 코드
    	for(int i = 0; i <= 99; i++) {
    		for(int j = 0; j <= 99; j++) {
    			if(map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) {
    				result++;
    			}
    		}
    	}
    	System.out.println(result);
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
	public static boolean isIn(int y, int x, int size){
        if(y < 0 || y == size + 1 || x < 0 || x == size + 1)
            return false;
        return true;
    }
}

총평

난이도

⭐⭐⭐⭐★

후기

어려워서 흰트를 보고 푼 문제.
잘 풀어 놓고, 경계값에서 틀려 고생을 좀 했다.

개선할 점

1. 적용해야 할 내용을 주석으로 달아 놓자
2. 경계값 분석은 할 수 있으면 꼭 하자
3. 문제의 입력 범위를 주석으로 적어 놓자