[java]드래곤 커브 - 백준15685

문제

• 드래곤 커브(백준15685)

풀이

문제 해석을 하자면,

• 문제를 이해하고 나면 어려운 문제는 아닌것 같은데, 문제를 처음 접해보면 이게 뭔가 싶다..
• 문제를 잘 읽어보고 “드래곤 커브 그리는 규칙” 발견을 하려고 노력하자
• 특히, 정사각형의 “네 꼭짓점”이 모두 드래곤 커브의 일부인 것들의 개수를 출력해야 한다.
  • “네 꼭짓점”을 안보고 정사각형만 읽었다가 문제를 한참 이해 못했었다ㅜㅜ

풀이

• 복잡도가 크지 않아서 “완전탐색”으로 접근하여 단순 “구현”하는 문제
• 두가지를 중점으로 풀이하면 된다.
  • (1) 드래곤 그리기 -> 방향이 어떻게 변화하는지 “규칙”찾는것이 중요
    • 입력으로 격자내부 범위 내용만 제공 참고
    • dx와 dy도 문제에 주어진 조건대로 만들 것
    • 입력 좌표 조심. 본인이랑 좌표 사용이 다름.
    • 그림 확인해보면 “스택”만 있어도 충분할 듯 -> 저장 시점 잘 확인
      • “변환”이란건 1,2,1,0 에 +1 씩 해서 2,3,2,1 로 만든걸 의미 -> “방향에 +1”
  • (2) 사각형 찾기(꼭짓점 체크) -> 네개씩 체크만 하면되어서 매우 간단

그림 참고

코드

public static int N;
public static boolean[][] visited = new boolean[205][205];
public static int dx[] = {0, -1, 0, 1};// 오른, 위, 왼쪽, 아래
public static int dy[] = {1,0,-1,0};

public static void main(String[] args) throws Exception {
    //init -> 백준 생략
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    for(int i=0; i<N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int y = Integer.parseInt(stk.nextToken()); // 좌표 조심
        int x = Integer.parseInt(stk.nextToken());
        int d = Integer.parseInt(stk.nextToken());
        int g = Integer.parseInt(stk.nextToken());
        //run
        // init -> 0세대
        visited[x][y]=true;//init
        int nx = x+dx[d];
        int ny = y+dy[d];
        visited[nx][ny]=true;//init -> 0세대 구함
        List<Pair> pArr = new ArrayList<>();
        // 1. 따로 배열에 기록
        pArr.add(new Pair(nx, ny, d));
        for(int k=0; k<g; k++) { // k세대 만큼 반복
            // 2. 스택에 다시할당 후 pop 사용
            Stack<Pair> st = new Stack<>(); // 매번 스택 새로 할당(초기화)
            for(int j=0; j<pArr.size(); j++) {
                st.push(pArr.get(j));
            }
            while(!st.isEmpty()) {
                Pair p = st.peek();
                st.pop();
                int nDir = (p.dir+1)%4;
                nx = nx+dx[nDir];
                ny = ny+dy[nDir];
                visited[nx][ny]=true;
                // 3. pop 끝나면 결과를 배열뒤에 이어 붙여주자
                pArr.add(new Pair(nx,ny,nDir)); // "다음좌표"와 "다음방향"을 기록
            }

        }
        // debug
        //      for(int j=0; j<pArr.size(); j++) {
        //        System.out.println(pArr.get(j));
        //      }
        //      System.out.println();
    }
    //output
    // 2. 사각형 찾기(꼭짓점 체크) -> 4개씩
    int result = 0;
    for(int i=0; i<105; i++) {
        for(int j=0; j<105; j++) {
            if(visited[i][j] && visited[i][j+1] && visited[i+1][j] && visited[i+1][j+1]) {
                result++;
            }
        }
    }
    System.out.println(result);

}
static class Pair {
    int x; int y; int dir;
    public Pair(int x, int y, int dir) {
        this.x=x; this.y=y; this.dir=dir;
    }
    @Override
    public String toString() {
        return "Pair [x=" + x + ", y=" + y + ", dir=" + dir + "]";
    }

}

느낀점

생략