백준 15685번: 드래곤 커브

문제 설명

• https://www.acmicpc.net/problem/15685
• 선분을 조건에 따라 계속해서 확장해 나가는 문제입니다.
  • 조건이란 마지막 끝점을 기준으로 90도 회전시키는 것을 말합니다.

접근법

• 문제의 핵심은 좌표를 90도 회전시키는 것과 개체수가 증가시키는 것입니다.
  1.좌표계 회전

  • 이전에 이러한 방식으로 좌표회전을 구현했던 적이 있습니다. (이전 풀이는 a와b가 절대값이 아니었습니다.)
    • 이번 문제를 풀어보니 거리를 절대값으로 구하고 + 혹은, -를 하는 게 편하다는 걸 느꼈습니다.
    • (2,3),(9,11)보다 (2,3),(2+7,3+8)으로 표현하는 게 훨씬 이해하기 편했습니다.
    • 

  2.개체수 증가

  • 세대를 거치면서 2^age개의 선이 생성됩니다.
  • 회전의 중심이 되는 중심축은 list의 가장 마지막 값이 되며,
  • 중심축을 제외한 list의 뒤쪽 데이터부터 가져와서 회전시킨 값을 넣어야 list에 올바른 순서로 데이터가 쌓입니다.
    • 이러한 속성때문에 처음에 Deque의 사용을 고려했지만, 특정 index의 값을 가져와야 하기 때문에 LinkedList로 구현 후 pollLast기능을 직접 구현했습니다.
  • 즉 (A,B,C)데이터가 들어있다면 C를 중심축으로 선택 후 B를 돌린 B'을 먼저 넣고, 그 다음 A를 돌린 A'을 넣어 (A,B,C,B',A')이 되어야 문제의 상황과 동일한 조건이 됩니다.

• 유의사항

  • 방향에 대한 혼동
    • 좌표계가 매우 이상합니다. (row,col)도 아니며 힌트를 보면 1사분면이 양수인 일반적인 (x,y)좌표계도 아닙니다. y가 증가하는 방향이↓인 문제입니다.
    • 회전이 재대로 구현되어 있다면 점수를 구할 때에는 board의 방향과 x,y의 방향을 맞출 필요는 없습니다.
  • 범위
    • 0<=x,y<=100입니다. 관성적으로 100을 제외한 범위를 생각하면 틀리게 됩니다.
  • 두 점이 x축 혹은 y축으로 평행한 경우
    • 특별한 예외처리가 필요하지 않습니다. 4개의 조건문이 각자 하나의 x 또는 y의 같다조건을 맡으면 됩니다.

      저는 다음과 같이 설정했습니다. <-> 이렇게 해도 상관없습니다.
      Mov.x>=Std.x && Mov.y>Std.y // Mov.x>Std.x && Mov.y>=Std.y
Mov.x<Std.x && Mov.y>=Std.y // Mov.x<=Std.x && Mov.y>Std.y
Mov.x<=Std.x && Mov.y<Std.y // Mov.x<Std.x && Mov.y<=Std.y
Mov.x>Std.x && Mov.y<=Std.y // Mov.x>=Std.x && Mov.y<Std.y

  • 좌표를 회전하는건 너무 헷갈리고 실수하기 쉽습니다. 종이에 그려보시는 걸 강력히 추천드립니다.
  • 코드구현에서 실수가 정말 많이 발생합니다. 최대한 모듈화하는 작업 및 조금 구현하고 바로바로 출력해서 결과값이 원하는대로 나오는지 확인하는걸 강력히 추천드립니다.

pseudocode

Main(){
    for(DragonCurve의 개수){
        주어진 입력마다 DragonCurve를 실행합니다.
    }
	Score() // 모든 커브를 완성한 후 점수를 계산합니다.
}


DragonCurve(x,y,d,age){
    좌표를 저장하는 list를 생성합니다.
    (x,y)와 (x+dx[d],y+dy[d])인 0세대를 list에 담습니다.
    for(1부터 age까지){
        현재 list에서 가장 뒤에 있는 값을 기준점으로 선정합니다.
        for(기준점 직전의 좌표->가장 처음좌표 순서로){
            list.add(Turn(기준점, 현재좌표)) // 현재좌표를 90도 회전한 좌표를 list에 넣습니다. (addLast)
        }
    }
}

Turn(기준점,돌려야 하는 점){
	xDist = 두 점의 x값 차이;
    yDist = 두 점의 y값 차이;
    if(돌려야 하는 점이 기준점의 오른쪽 아래에 있으면){
    	새로운 점 = 기준점.x-yDist,기준점.y+Xdist;
    }
	if(돌려야 하는 점이 기준점의 왼쪽 아래에 있으면){
    	새로운 점 = 기준점.x-yDist,기준점.y-Xdist;    
    }
    if(돌려야 하는 점이 기준점의 왼쪽 위에 있으면){
    	새로운 점 = 기준점.x+yDist,기준점.y-Xdist;
    }
    if(돌려야 하는 점이 기준점의 오른쪽 위에 있으면){
    	새로운 점 = 기준점.x+yDist,기준점.y+Xdist;
    }
    return 새로운 점
}

Score(){
	for(0부터99까지){
    	for(0부터99까지){
        	if(4개의 점이 모두 true라면) cnt++;
        }    
    }
	return cnt;
}

정답

import java.util.*;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,-1,0,1};
	static boolean[][] board;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		board = new boolean[101][101];
		int N = sc.nextInt();
		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int d = sc.nextInt();
			int age = sc.nextInt();
			DragonCurve(x,y,d,age);
		}
		System.out.println(Score());
	}
	

	public static void DragonCurve(int x, int y, int d, int age) {
		List<pos> lst = new LinkedList<pos>();
		// 0세대
		lst.add(new pos(x,y));
		lst.add(new pos(x+dx[d],y+dy[d]));
		
		for (int a = 1; a <= age; a++) {
			int size = lst.size();
			pos Std = lst.get(size-1);// 기준점
			for (int i = size-1-1; i >=0; i--) { // 기준점을 제외한 lst의 모든 원소를 의미합니다.
				lst.add(Turn(Std,lst.get(i))); // 회전한 좌표를 lst에 넣습니다.
			}
		}
        
        // 드래곤커브를 완성 후 board에 좌표를 표시하는 작업입니다.
		for (int i = 0; i < lst.size(); i++) {
			pos temp = lst.get(i);
			if(0<=temp.x && temp.x < 101 && 0<=temp.y && temp.y < 101) { 
				board[temp.x][temp.y] = true;
			}
		}
		
	}
	
	public static pos Turn(pos Std, pos Mov) {
		int xDist = Math.abs(Std.x-Mov.x);
		int yDist = Math.abs(Std.y-Mov.y);
        // 중심축을 기준으로 비교대상이 어디 위치하느냐에 따라 결과값이 다릅니다.
		if(Mov.x>=Std.x && Mov.y>Std.y) { // 좌표계 회전에 첨부한 그림을 기준으로 회전할 좌표가 4사분면에 있으면
			return(new pos(Std.x-yDist,Std.y+xDist));
		}
		if(Mov.x<Std.x && Mov.y>=Std.y) { // 좌표계 회전에 첨부한 그림을 기준으로 회전할 좌표가 3사분면에 있으면
			return(new pos(Std.x-yDist,Std.y-xDist));
		}
		if(Mov.x<=Std.x && Mov.y<Std.y) { // 좌표계 회전에 첨부한 그림을 기준으로 회전할 좌표가 2사분면에 있으면
			return(new pos(Std.x+yDist,Std.y-xDist));
		}
		if(Mov.x>Std.x && Mov.y<=Std.y) { // 좌표계 회전에 첨부한 그림을 기준으로 회전할 좌표가 1사분면에 있으면
			return(new pos(Std.x+yDist,Std.y+xDist));
		}
		return Std;
	}
	
	public static int Score() {
		int cnt = 0;
		for (int i = 0; i <= 99; i++) {
			for (int j = 0; j <= 99; j++) {
				if(board[i][j] && board[i+1][j] && board[i][j+1] && board[i+1][j+1]) cnt++;
			}
		}
		return cnt;
		
	}
	
	static class pos{
		int x;
		int y;
		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}
	}
}

기타

• 꼭지점이 아니라 선분이 모두 연결된 경우를 count해야 했으면 어땠을까?