[백준/C++] 하이퍼 토마토

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 사실 BFS를 풀 줄 알면 쉽게 해결할 수 있는 문제다.

하지만, 11차원이라는 점에서 그렇게 되면 거의 반 노가다 문제가 된다.

 

그래서 어떻게 하면 코드를 효율적으로 짤 수 있을까? 생각을 하다가, 1차원 배열로 토마토들을 배치한 뒤 인접 이동을 +1,-1이 아니라 n칸씩 이동하면 되겠다는 생각이 들었다.

 

간단한 예를 생각해 보자

만약 차원이 [3 2 2 1 1 1 1 1 1 1 1]로 주어진다면 토마토를 이렇게 표현할 수 있다.

파란색으로 표시된 부분은 2번 토마토가 다른 토마토를 익게 할 수 있는 범위다.

즉, 인접한 토마토들의 위치와 index차이를 나타낸 것이다.

 

잘 보면 [3 2 2]에서 인접한 토마토와의 index차이가 [1, 3, 6]임을 알 수 있다.

그러므로 이를 이용하면 단순히 1차원으로도 인접한 토마토가 어떤 토마토인지 쉽게 파악할 수 있게 된다.

 

이후 이 인접 토마토 index를 이용해 BFS로 문제를 풀면 쉽게 해결할 수 있다.

 

+ 여기서 1차원으로 문제를 풀면 추가로 고려해야할게 하나 있다.

5번 토마토가 +3의 index를 더한 값인 8번 토마토와 인접해 있다고 착각할 수 있다.

하지만 실제로 5번 토마토와 8번 토마토는 인접해 있지 않다.

5번 토마토가 [3 2 2]에서 2의 마지막 줄이므로 더 이상 +3 방향으로는 인접한 토마토가 없기 때문이다.

(1차원이라 있는 것처럼 느껴지지만, 실제로는 없다.)

이를 나누기와 %연산을 잘 사용해 n차원의 마지막 줄인지 판단하는 것을 추가해야한다.

ex) 0<=dx<size(x) 와 같이 범위 체크를 해야한다는 뜻이다.

 

 

 

​

[아이디어 정리]

1. 토마토의 배치를 1차원으로 나타낸다.
2. 인접한 토마토를 표현하기 위해 곱셈을 이용해 index가 얼마만큼 차이나야 인접해 있는지를 알 수 있는 값을 저장한다.
3. 저장한 값을 이용해 인접한 토마토가 있으면 익도록 BFS를 구현한다.
4. 최종적으로 익은 토마토를 확인하고 전부 익었으면 익은 날짜를 출력하고 전부 익지 않았다면 -1을 출력한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

bool canGo(vector<int>& map, vector<int>limitD, vector<int>dx, int nD, int limitIdx, int seat)
{
    int nS = seat + dx[limitIdx];
    if (limitIdx % 2 == 0)
    { // 위로 +
        if (seat % limitD[nD] + dx[limitIdx] < limitD[nD] && map[nS] == 0) {
            map[nS] = 1;
            return true;
        }
    }
    else { //아래로
        if (seat % limitD[nD] >= dx[nD * 2] && map[nS] == 0) {
            map[nS] = 1;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> nDemension;
    int d;
    for (int i = 0; i < 11; i++) {
        cin >> d;
        if (d > 1) {
            nDemension.push_back(d);
        }
    }

    int moveF = 1;
    vector<int> dx;
    vector<int> limitD(nDemension.size());
    for (int i = 0; i < nDemension.size(); i++) {
        dx.push_back(moveF);
        dx.push_back(-moveF);
        moveF *= nDemension[i];
        limitD[i] = moveF;
    }
    vector<int>map(moveF);
    queue<pair<int, int>> q;
    int toma = 0;
    for (int i = 0; i < moveF; i++) {
        cin >> map[i];
        if (map[i] == 1) {
            q.push({ i, 0 });
        }
        else if (map[i] == 0) {
            toma += 1;
        }
    }

    pair<int, int> np;
    int lstD = 0;
    while (!q.empty()) {
        np = q.front();
        lstD = np.second;
        q.pop();
        for (int i = 0; i < nDemension.size(); i++) {
            for (int j = 0; j < 2; j++) {
                if (canGo(map, limitD, dx, i, i * 2 + j, np.first))
                {
                    q.push({ np.first + dx[i * 2 + j] , np.second + 1 });
                    toma -= 1;
                }
            }
        }
    }
    if (toma == 0) {
        cout << lstD;
        return 0;
    }
    cout << -1;
    return 0;
}

 

---

구현된 코드가 생각보다 시간이 오래 걸리는 코드다.

1차원으로 구현하다보니 중간에 비 효율적인 부분이 생긴 것 같은데, 어떤 부분에서 시간이 오래걸리는지 확인하고 나중에 시간을 줄여봐야겠다... ㅠㅠ

 

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