[구현] Struct/Class 활용 + 헤더 분리 연습 (BOJ 16235 나무 재테크)

클래스를 활용한 구현/시뮬레이션 문제 풀이 기록.

구현 시, 여러 가지 정보를 담고 있는 개체가 등장할 경우, class 혹은 struct으로 구현해주는게 깔끔함

 

나무를 어떻게 관리할 것인가?
한 칸에 여러 개의 나무 어떻게 정보 저장? 데이터구조 뭐 써?
> 각 칸에 있는 나무들을 나이 순으로 저장해야 함; 각 칸의 죽은 나무도 따로 저장;
=> class 만들고, NxN 크기의 class 배열 만들어야겠다.

 

* 되도록이면 코딩테스트에선 public으로 변수 선언하기 (get 메소드 등 쓰기보다는 직접 멤버 변수 바꿔서 시간 절약)

// main.cpp

#include <bits/stdc++.h>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define FOReq(i, m, n) for(int i = (m); i <= (n); ++i)
#define all(c) (c).begin(), (c).end()
using namespace std;

using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using pii = pair<int, int>;
const int INF = 1e9;

int N, K;
vector<vi> arr;

// ★ Class 활용
class Garden {
    vi live; // 봄마다 정렬해야하는데 TLE 위험; set으로 바꾸면? (multiset 써야겠네.. 중복되는게 많으니, 삭제할때 중복되는거 다 삭제 아님?)
    // vi dead;
    int food;

public:
    Garden() :food(5) {};
    void spring();
    void summer();
    void fall(int x_s, int y_s);
    void add_tree(int age) { live.push_back(age); }
    void add_food(int f) { food += f; }
    int count_tree() { return live.size(); }
};
vector<vector<Garden>> Field;


void Garden::spring() {
    sort(all(live));

    int dead_pos = live.size();
    FOR(i, 0, live.size()){
        int& age = live[i];
        if (age <= food) {
            food -= age;
            age++;
        }
        else {
            dead_pos = i;
            break;
        }
    }

    // 바로 여름 처리 ★
    while (live.size() - dead_pos) {
        //dead.push_back(live.back()); // dead 필요 없을 듯
        food += live.back() / 2;
        live.pop_back();
    }

    // Garden::summer();
}

void Garden::summer(){
    // 필요 없음
}


void Garden::fall(int x_s, int y_s){
    auto Boundary = [&](int x, int y) {return 1 <= x && x <= N && 1 <= y && y <= N;};
    
    for(int age : live) {
        if (age % 5 == 0) {
            // Plant new tree
            FOR(i, 0, 8){
                int nx = x_s + "00011222"[i] - '1'; // ★ 빠르고 깔끔한 좌표 탐색 방법
                int ny = y_s + "01202012"[i] - '1';

                if (!Boundary(nx, ny)) continue;
                Field[nx][ny].add_tree(1);
            }
        }
    }
}

void winter() {
    FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].add_food(arr[x][y]);
}

int main() {
#ifdef DBG
    freopen("../input.txt", "r", stdin);
#endif
    fastio;

    int M;
    cin >> N >> M >> K;

    Field = vector<vector<Garden>>(N+1, vector<Garden>(N+1)); // ★ 클래스 벡터 이렇게 초기화 가능

    arr = vector<vi>(N+1, vi(N+1));
    FOReq(x, 1, N) FOReq(y, 1, N) cin >> arr[x][y];
    
    int x, y, age;
    FOR(tree, 0, M) {
        cin >> x >> y >> age;
        Field[x][y].add_tree(age);
    }

    while (K--) {
        FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].spring();
        FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].fall(x, y);
        winter();
    }

    int total = 0;
    FOReq(x, 1, N) FOReq(y, 1, N) total += Field[x][y].count_tree();
    cout << total;
}

 

Plain-Old-Data의 경우, struct을 쓰는게 깔끔하다

(struct도 constructor, 멤버 함수 등 선언 가능; 다 public이라는 차이밖에)

goldenriver42.tistory.com/34?category=944792

struct _PB {
    int x, y, d;
    
    _PB(int _x, int _y, int _d) :x(_x), y(_y), d(_d) {};
    void d_ch() { d = (d + 2) % 4; }; // Change direction straightly
    int move();
} PB; // 이러면 PB 바로 쓰기 가능

int _PB::move() {
	...
}

 

관련 문제)

BOJ 17143 - 낚시왕

삼성 SW 역량테스트 상어 시리즈

 

 

Garden의 선언 및 멤버 함수 구현부를 main.cpp에서 분리할 수 없을까?

Garden.h, Garden.cpp로 분리 가능!

 

<Garden.h>

// Garden.h

#pragma once // 중복 선언 방지
#include <vector> // vector 이용하기 때문에 필요
using std::vector;

class Garden {
private:
	vector<int> live;
	int food;

public:
	Garden() :food(5) {};
	void spring();
	void summer();
	void fall(int x_s, int y_s, int N, vector<vector<Garden>>& Field);
	void add_tree(int age) { live.push_back(age); }
	void add_food(int f) { food += f; }
	int count_tree() { return live.size(); }
};

 

<Garden.cpp>

// Garden.cpp

#include "Garden.h"
//#include <bits/stdc++.h>
#include <algorithm>

#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define FOReq(i, m, n) for(int i = (m); i <= (n); ++i)
#define all(c) (c).begin(), (c).end()

void Garden::spring() {
	std::sort(all(live));

	int dead_pos = live.size();
	FOR(i, 0, live.size()) {
		int& age = live[i];
		if (age <= food) {
			food -= age;
			age++;
		}
		else {
			dead_pos = i;
			break;
		}
	}

	// 바로 여름 처리 ★
	while (live.size() - dead_pos) {
		//dead.push_back(live.back()); // dead 필요 없을 듯
		food += live.back() / 2;
		live.pop_back();
	}

	// Garden::summer();
}

void Garden::summer()
{
}

void Garden::fall(int x_s, int y_s, int N, vector<vector<Garden>>& Field) {
	auto Boundary = [&](int x, int y) {return 1 <= x && x <= N && 1 <= y && y <= N;};

	for (int age : live) {
		if (age % 5 == 0) {
			// Plant new tree
			FOR(i, 0, 8) {
				int nx = x_s + "00011222"[i] - '1'; // ★ 빠르고 깔끔한 좌표 탐색 방법
				int ny = y_s + "01202012"[i] - '1';

				if (!Boundary(nx, ny)) continue;
				Field[nx][ny].add_tree(1);
			}
		}
	}
}

 

<main.cpp>

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define FOReq(i, m, n) for(int i = (m); i <= (n); ++i)
#define all(c) (c).begin(), (c).end()
using namespace std;

using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using pii = pair<int, int>;
const int INF = 1e9;

#include "Sandbox/Garden.h" // ★ Garden 관련 선언/구현부 분리

int N, K;
vector<vi> arr;
vector<vector<Garden>> Field;

void winter() {
	FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].add_food(arr[x][y]);
}

int main() {
#ifdef DBG
	freopen("../input.txt", "r", stdin);
#endif
	fastio;

	int M;
	cin >> N >> M >> K;

	Field = vector<vector<Garden>>(N+1, vector<Garden>(N+1));

	arr = vector<vi>(N+1, vi(N+1));
	FOReq(x, 1, N) FOReq(y, 1, N) cin >> arr[x][y];
	
	int x, y, age;
	FOR(tree, 0, M) {
		cin >> x >> y >> age;
		Field[x][y].add_tree(age);
	}

	while (K--) {
		FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].spring();
		FOReq(x, 1, N) FOReq(y, 1, N) Field[x][y].fall(x, y, N, Field); // ★ 필요한 전역변수 패스 (Q. 너무 지저분한가?)
		winter();
	}

	int total = 0;
	FOReq(x, 1, N) FOReq(y, 1, N) total += Field[x][y].count_tree();
	cout << total;
}

 

분리하며 겪었던 문제점)

- Garden.h 에는 최대한~반드시 Garden과 관련된 선언만 넣는게 중요

Garden::fall에 전역 변수인 N과 Field가 쓰여서, Garden.h로 N과 Field 선언을 옮겼더니 main.o와 중복되는 선언이 있다며 난리남 → 전역 변수 선언은 main.cpp에 두고, Garden::fall에 레퍼런스 패스하는 식으로 고쳐서 해결

 

좋은 점)

main.cpp를 비롯해서 전체적으로 코드가 분할되어 깔끔해짐. 유지/보수에 정말 좋을 듯.