백준 16235 나무 재테크

예제가 너무 많아서 사진은 조금 생략..

 

앞에 풀었던 아기 상어 문제가 시뮬레이션 문제라는 것을 풀고 나서 알았다..

주어진 조건에 맞게 풀면 되는 문제가 시뮬레이션이라고 한다.

 

이번 문제도 시뮬레이션 문제이다. 주어진 조건에 맞춰서 풀면 된다.

사람마다 당연히 코드는 다르겠지만, 뭔가 코드가 보기 힘들게 짜여진 것 같긴하다. 앞으로 보완해야 겠다.

 

처음에 입력받는 A배열을 겨울에 더해주어야 하는데 처음부터 더해주어서 계속 틀렸다. 문제도 꼼꼼히 읽어봐야 겠다.

나무는 추가되고 삭제되기 때문에 편하도록 vector로 저장했다. 특히, 3차원 vector를 만들어주었다. 3차원 vector는 처음 써보아서 눈에 잘 익혀둬야 할 필요성을 느꼈다.

삭제로는 erase 함수를 사용했는데, 해당 인덱스 원소가 지워지면 뒤에 있는 원소들이 한 칸씩 앞으로 땡겨지는 것을 모르고 있었다. 이를 주의해야겠다.

 

나머지는 조건에 맞춰서 코딩해주었다. 코드는 아래와 같다.(중간 중간 디버깅을 위한 코드를 주석처리 해놓았다.)

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
 
int land[10][10];
int cp_land[10][10];
//나무는 한 공간에 여러 개가 있을 수 있기 때문에 3차원 vector로 만든다.
//3차원 vector 사용법 익히기
vector<vector<vector<int>>> trees(10, vector<vector<int>>(10,vector<int>()));
 
//8방향 이동 편의를 위한 배열
int dr[8] = { -1,-1,0,1,1,1,0,-1 };
int dc[8] = { 0,1,1,1,0,-1,-1,-1 };
 
int main(int argc, char** argv) {
    int n, m, k;
    cin >> n >> m >> k;
    //처음 심은 나무만큼 답에 대입
    int ans = m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &land[i][j]);
            cp_land[i][j] = 5;
        }
    }
    for (int i = 0; i < m; i++) {
        int row, col, age;
        cin >> row >> col >> age;
        //입력이 1,1부터 시작되므로 1씩 빼준다.
        trees[row-1][col-1].push_back(age);
    }
 
    //int cnt = 1;//디버깅 용도
 
    //k년 동안 loop
    while (k--) {
        //죽은 나무 저장하기 위한 vector
        vector<tuple<int, int, int, int>> died;
        //봄: 나이만큼 양분을 먹는다.(나무가 1개 이상이면 어린 나무부터 먹는다.), 나이만큼 못 먹으면 즉시 죽는다. 나이가 1증가한다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //나무가 1개 이상이면 sorting
                if (trees[i][j].size() > 1)sort(trees[i][j].begin(), trees[i][j].end());
                //양분을 먹을 수 있는 나무들은 계속 먹는다.
                for (int l = 0; l < trees[i][j].size(); l++) {
                    //양분을 먹은 나무는 나이가 증가한다.
                    if (cp_land[i][j] - trees[i][j][l] >= 0) {
                        cp_land[i][j] -= trees[i][j][l];
                        trees[i][j][l]++;
                    }
                    else {//못 먹으면 즉시 죽는다.(하지만 여름에 양분을 줘야 하니까 죽은 나무 vector에 추가한다.)
                        died.push_back(make_tuple(i, j, trees[i][j][l], l));
                        //나무 삭제
                        //erase함수 사용법 익히기
                        trees[i][j].erase(trees[i][j].begin() + l);
                        //erase는 지우면 한칸씩 땡기기 때문에 l도 1감소시킨다.
                        l--;
                        //답에서 1지움
                        ans--;
                    }
                }
            }
        }
        /*출력 부분(디버깅)
        printf("봄 이후 양분상태\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%2d ", cp_land[i][j]);
            }
            printf("\n");
        }
        printf("\n나무 현황\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("(");
                if (trees[i][j].size() == 0)printf("0 ");
                for (int l = 0; l < trees[i][j].size(); l++) {
                    printf("%d ", trees[i][j][l]);
                }
                printf(")");
            }
            printf("\n");
        }
        printf("\n");*/
        
        //여름: 죽은 나무 나이/2 만큼 양분이 된다. 소수점은 버린다.
        for (int i = 0; i < died.size(); i++) {
            int row, col, age, idx;
            tie(row, col, age, idx) = died[i];
            cp_land[row][col] += age / 2;
        }
        /*출력 부분(디버깅)
        printf("여름 이후 양분상태\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%2d ", cp_land[i][j]);
            }
            printf("\n");
        }
        printf("\n나무 현황\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("(");
                if (trees[i][j].size() == 0)printf("0 ");
                for (int l = 0; l < trees[i][j].size(); l++) {
                    printf("%d ", trees[i][j][l]);
                }
                printf(")");
            }
            printf("\n");
        }
        printf("\n");*/
 
        //가을: 나무의 나이가 5의 배수이면 번식한다. 인접한 8칸에 나이가 1인 나무를 생성한다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (trees[i][j].size() == 0)continue;
                //나무가 있으면 5의 배수인지 check하고 인접한 8칸에 나무 생성
                for (int l = 0; l < trees[i][j].size(); l++) {
                    if (trees[i][j][l] % 5 == 0) {
                        for (int x = 0; x < 8; x++) {
                            int nr = i + dr[x];
                            int nc = j + dc[x];
 
                            if (nr < 0 || nr >= n || nc < 0 || nc >= n)continue;
                            trees[nr][nc].push_back(1);
                            //생성한 만큼 답에 추가
                            ans++;
                        }
                    }
                }
            }
        }
        /*출력 부분(디버깅)
        printf("가을 이후 양분상태\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%2d ", cp_land[i][j]);
            }
            printf("\n");
        }
        printf("\n나무 현황\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("(");
                if (trees[i][j].size() == 0)printf("0 ");
                for (int l = 0; l < trees[i][j].size(); l++) {
                    printf("%d ", trees[i][j][l]);
                }
                printf(")");
            }
            printf("\n");
        }
        printf("\n");*/
 
        //겨울: 처음 입력으로들어온 만큼 양분 증가
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cp_land[i][j] += land[i][j];
            }
        }
 
        /*출력부분(디버깅)
        printf("----------%d년 농사 끝!!--------", cnt++);
        printf("양분상태\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%2d ", cp_land[i][j]);
            }
            printf("\n");
        }
        printf("\n나무 현황\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("(");
                if (trees[i][j].size() == 0)printf("0 ");
                for (int l = 0; l < trees[i][j].size(); l++) {
                    printf("%d ", trees[i][j][l]);
                }
                printf(")");
            }
            printf("\n");
        }
        printf("\n");
        */
    }
 
    printf("%d\n", ans);
 
    return 0;
}

============================================================================

c++로 할 때는 그냥 3차원 vector를 사용해서 풀었었다.

하지만 java로 다시 풀면서 arraylist를 사용해서 2차원 배열의 arraylist를 만들어서 풀려고 했더니 시간 초과가 떳다.

어떻게 효율적으로 할까 오랫동안 생각해보았다.

나이가 어린 나무를 먼저 체크해야 하기 때문에 sorting이 필요함을 알았지만, 하나의 arraylist에 모든 나무를 다 넣고 sorting을 하면 될까 하는 생각이 들었다. 좌표값과 나이를 모두 sorting 조건에 넣어야 한다고만 생각해서 이를 제외하고 다른 방법들을 생각했었다.

하지만 trees라는 arraylist에서 age만 가지고 sorting을 하면 결국 map에 있는 남은 양분과 age를 비교해서 나무를 살리고 죽이는 것이기 때문에 문제가 없었다.

다시 말하면 2차원 배열에 갇혀서 row와 col값을 하나씩 확인하면서 해당 칸에 있는 나무들을 정렬하려 했지만, 사실 좌표값에 따른 순서는 상관이 없었고(좌표는 상관이 없음), 좌표에 상관없이 모든 나무들의 age가 어린 나무들을 해당 좌표의 양분에 빼주기만 하면 되는 거였다.

조금만 더 생각해서 조금만 더 나가면 되는 건데 이를 생각하지 못했다..

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int ans;
    static int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
 
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = 5;
            }
        }
 
        int ans = 0;
        int[][] yang = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                yang[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        ArrayList<int[]> trees = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
 
            int[] temp = { row, col, age };
            trees.add(temp);
            ans++;
        }
 
        for (int i = 0; i < k; i++) {
            // 봄
            ArrayList<int[]> dead = new ArrayList<>();
            Collections.sort(trees, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[2] > o2[2])
                        return 1;
                    else if (o1[2] < o2[2])
                        return -1;
                    else
                        return 0;
                }
            });
            ArrayList<int[]> alive = new ArrayList<>();
            for (int j = 0; j < trees.size(); j++) {
                int row = trees.get(j)[0];
                int col = trees.get(j)[1];
                int age = trees.get(j)[2];
 
                if (map[row][col] < age) {
                    int[] temp = { row, col, age };
                    dead.add(temp);
                    ans--;
                    continue;
                }
                map[row][col] -= age;
                trees.get(j)[2]++;
                alive.add(trees.get(j));
            }
            trees = alive;
 
 
            // 여름
            for (int j = 0; j < dead.size(); j++) {
                int row = dead.get(j)[0];
                int col = dead.get(j)[1];
                int age = dead.get(j)[2];
 
                map[row][col] += age / 2;
            }
 
            // 가을
            for (int j = 0; j < trees.size(); j++) {
                int row = trees.get(j)[0];
                int col = trees.get(j)[1];
                int age = trees.get(j)[2];
 
                if (age % 5 == 0) {
                    for (int dir = 0; dir < 8; dir++) {
                        int nr = row + dr[dir];
                        int nc = col + dc[dir];
                        if (nr < 0 || nr >= n || nc < 0 || nc >= n)
                            continue;
 
                        int[] temp = { nr, nc, 1 };
                        trees.add(temp);
                        ans++;
                    }
                }
 
            }
 
            // 겨울
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    map[x][y] += yang[x][y];
                }
            }
 
        }
        System.out.println(ans);
    }
 
}