https://www.acmicpc.net/problem/15685

배울 게 많았던 문제.
마찬가지로 삼성 SW 역량테스트 기출문제이다.

문제 설명 및 입출력

문제에서 추출할 수 있는 정보는 다음과 같다.

• N세대 드래곤 커브는 (N-1) 세대 드래곤 커브만큼 90도 시계방향에서 다시 실행하면 된다.
• 즉 2세대 드래곤 커브는 서로 방향이 다른 1세대 드래곤 커브 2세트이다.
• 전체 격자를 순회하며 1x1 정사각형을 이루는 인접한 네 꼭짓점의 모든 경우의 수를 구하면 된다.

해결 과정

먼저 총 N번의 시행으로 누적된 꼭짓점들로 결과를 산출하기 때문에 방문 여부를 나타내는 visited는 최초 한 번만 초기화하면 된다.

0세대의 경우 현재 좌표에서 특정 방향으로 움직이기만 하면 된다.

1세대의 경우그림에서 알 수 있듯이 현재 좌표에서 초기 방향의 90도 반시계방향으로 움직인다.

2세대의 경우 약간 복잡해진다. 원본 1세대의 움직임은 우 > 상이었다.
다른 방향의 1세대의 움직임은 좌 > 상이 되었다.

3세대까지 살펴보면 규칙을 알 수 있다.
원본 2세대의 움직임은 우 > 상 > 좌 > 상이었다.
다른 방향의 2세대의 움직임은 좌 > 하 > 좌 > 상이 되었다.

기존의 누적된 방향들을 역으로 순회하며 오리지널 방향의 반시계 방향으로 움직임을 확인하였다.

다시 말해서 직전 세대 기준 이때까지의 진행 방향을 역으로 순회하며 방향을 반시계방향으로 개편한 뒤 이를 움직임에 반영하면 된다.

재귀함수를 활용할 때 g가 0일 수 있음에 주의하자.
(g는 무조건 1부터 시작한다고 생각했다가 시간을 날렸다.)

소스 코드

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int n, x, y, d, g;
bool visited[101][101];
int dx[4] = {0, -1, 0, 1}; // 우상좌하
int dy[4] = {1, 0, -1, 0};
vector<int> path; // 누적되는 방향

void curve(int cnt){
    if(cnt > g) return; // 종료조건
    if(cnt == 0){ // 초기조건
        visited[x][y] = true;
        x = x + dx[d];
        y = y + dy[d];
        path.push_back(d);
        visited[x][y] = true;
        curve(cnt+1);
    } else {
        for(int i=path.size()-1; i>=0; i--){
            d = (path[i] + 1) % 4;
            x = x + dx[d];
            y = y + dy[d];
            visited[x][y] = true;
            path.push_back(d);
        }
        curve(cnt+1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(visited, 0, sizeof(visited));

    cin >> n;
    for(int i=0; i<n; i++){
        path.clear(); // 매 케이스별로 초기화
        cin >> y >> x >> d >> g;
        curve(0);
    }

	// 1x1 정사각형을 이루는 네 꼭짓점의 경우의 수
    int a = 0;
    for(int i=0; i<100; i++){
        for(int j=0; j<100; j++){
            if(visited[i][j] && visited[i+1][j] && visited[i][j+1] && visited[i+1][j+1]){
                a++;
            }
        }
    }
    cout << a;
    return 0;
}

교훈

• 재귀함수를 활용해야 할 때는 어떤 행동이 어떤 결과를 불러일으키는지에 대한 명확한 정리가 먼저 필요하다.
• 재귀함수는 초기조건, 종료조건 설정이 가장 중요하다.