구현

백준 15685번 구현 문제를 Java로 풀어보았다.
문제를 이해하는 데만 20분 정도만 걸렸다. 물론 내가 멍청해서 오래 걸린 거긴 한데...그래도 문제가 상당히 길고 처음 볼 때는 복잡해보였다.

하지만 방향성 규칙만 한 번 잡히고 나면 생각보다 간단한 문제다. 문제가 너무 길기 때문에 링크만 첨부한다.
https://www.acmicpc.net/problem/15685

---

방향이 바뀌는 규칙

방향이 어떤 규칙을 가지고 변하는지 알아보겠다고 나름 끄적댄 흔적이다. 사실 방향 규칙은 몇 개만 커브를 그려보면 바로 눈에 보이긴 한다.

1. 0 -> 1
2. 1 -> 2
3. 2 -> 3
4. 3 -> 0

위와 같은 규칙으로 방향이 바뀌는 것을 알 수 있다. 이를 수학적으로 표현해주면 +1 then %4로 표현이 가능하다.
방향 리스트를 만들 때 주의해야 할 것은 이전 커브의 끝에서 새로운 커브가 시작된다는 것만 신경써주면 된다. 이는 아래에서 보겠지만, 반복문을 통해 방향 리스트를 작성할 때 쓰이는 조건으로 들어가기 때문에 꼭 주의해야 한다.

이를 코드로 표현해보면 다음과 같다.

ArrayList<Integer> directionList = new ArrayList<>();
directionList.add(startDir);
/** 밟게될 모든 방향들 저장해주자 */
for(int i=0; i<gen; i++){
    int size = directionList.size();
    int idx = size;
    for(int j=size-1; j>=0; j--){ // 이전 커브의 끝에서 새로운 커브 시작!!
        int tmpDir = directionList.get(j);
            directionList.add((tmpDir+1)%4); // 0->1, 1->2, 2->3, 3->0
        }
    }

이렇게 모든 방향을 다 얻게 됐으면 다음으로는 그 방향대로 움직이며 map에 점을 찍어주면 된다.

방향따라 점 찍기

위에서 얻은 방향 리스트를 이용해서 점을 찍어보자.

/** 이제 방향대로 쭉 점 찍어주자*/
        map[startY][startX] = 1;
        for(int i=0; i<directionList.size(); i++){
            int tmpDir = directionList.get(i);
            startY += move[tmpDir][0]; startX += move[tmpDir][1];
            map[startY][startX] = 1;
        }

정사각형이 몇 개인지 세보자

위에서 점을 찍어둔 map을 돌며 점 찍힌 곳을 만날 때마다 그 점과 함께 정사각형을 이루는 점들에 흔적이 있는지 확인해보자.

static Integer checkSquare(){ // 찍힌 점들을 통해 정사각형 개수 세는 메소드
        int result = 0;
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if (map[i][j]==1 && map[i][j+1]==1 && map[i+1][j]==1 && map[i+1][j+1]==1) {
                    result++;
                }
            }
        }
        return result;
    }

---

자! 이로써 정사각형 개수를 세기 위한 3단계가 모두 완성됐다! 이를 하나로 합친 코드를 보자. 아래는 내가 제출한 코드다.

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

public class boj15685 {
    static int N;
    static Info[] list;
    static int[][] map = new int[101][101];
    static int[][] move = { {0,1}, {-1,0}, {0,-1}, {1,0} };

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        list = new Info[N];
        for(int i=0; i<N; i++){ // 커브 정보 입력받자
            stk = new StringTokenizer(bfr.readLine());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());
            int dir = Integer.parseInt(stk.nextToken());
            int gen = Integer.parseInt(stk.nextToken());
            list[i] = new Info(x,y,dir,gen);

            drawDots(list[i]);
        }

        bfw.write(String.valueOf(checkSquare()));
        bfw.close();
    }

    static void drawDots(Info target){ // 밟는 모든 점들 찍어주는 메소드
        int startX = target.x; int startY = target.y;
        int startDir = target.dir; int gen = target.gen;

        ArrayList<Integer> directionList = new ArrayList<>();
        directionList.add(startDir);
        /** 밟게될 모든 방향들 저장해주자 */
        for(int i=0; i<gen; i++){
            int size = directionList.size();
            int idx = size;
            for(int j=size-1; j>=0; j--){
                int tmpDir = directionList.get(j);
                directionList.add((tmpDir+1)%4); // 0->1, 1->2, 2->3, 3->0
            }
        }
        /** 이제 방향대로 쭉 점 찍어주자*/
        map[startY][startX] = 1;
        for(int i=0; i<directionList.size(); i++){
            int tmpDir = directionList.get(i);
            startY += move[tmpDir][0]; startX += move[tmpDir][1];
            map[startY][startX] = 1;
        }
    }

    static Integer checkSquare(){ // 찍힌 점들을 통해 정사각형 개수 세는 메소드
        int result = 0;
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if (map[i][j]==1 && map[i][j+1]==1 && map[i+1][j]==1 && map[i+1][j+1]==1) {
                    result++;
                }
            }
        }
        return result;
    }

    static class Info{
        int x,y,dir,gen;
        Info(int x, int y, int dir, int gen){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.gen = gen;
        }
    }
}