[アルゴリズム解析]BOJ 16432打餅行商人とトラ

ああ...まったく.これは前例のない難題だ.
昨日.2つ目の問題を選び、今日の午後4時に解決した状況です.
要するに、昨日から今日まで解決した問題はBOJ 16432菓子屋とトラです.

BOJ 16432菓子屋とトラ

餅売りの東希は毎朝、出来立ての餅を持って峠を越えて市場に行って餅を売りに行きます.東熙が作った餅の種類は1番から9番までです
山の中にトラが住んでいて、東希が現れるのを待っていて、東希に餅を持っていくように脅しました.このトラは食欲がなく、前日食べた餅と同じ種類なら食べません.与えられるお餅がなかったら、東希はトラに食べてくれてありがとう.
東希は市場に行って餅を売って、N日間売った.東熙が作った餅の種類は材料の供給状況によって毎日違う.
東熙がトラに食べられないように、トラに食べさせる餅を選んでください.

にゅうしゅつりょく

私の答え

いいえ.これは私の答えではありません.イライラしています.ううう、ううう、悲しいです.
最初は2つのアプローチを考えました.
私はただ、すべての状況を簡単に考えて、何か方法があって、時間を減らすことができるかどうかを考えています.
確認のために簡単な方法でコードを記述して再生したが,予想通りタイムアウトが発生した.
繰り返しの状況や探索を必要としない状況を事前に判断し,時間を減らす必要がある.
しかし、私は結局自分の力でこの部分を考えることができませんでした.
アクセスチェックのために3次元配列を使うべきだと思いますが、最終的には他の人の位置を見て解決しました.
アクセスの有無を確認する2 D配列visitedの意味は次のとおりです.visited[i][j]=i-1日でj号餅を食べに行ったことを確認しましたか!
その日ではなく前日食べたお餅を記録していたので混同!
配列visitedの意味を覚えてから,DFS探索を再帰的に行う.
dayが持っていった餅の中から1つ(riceCake[day][i])を探索していない場合、この餅を選択してday+1日で行った場合、最終正解配列answerのanswer[day]に餅を格納し、関数を再呼び出します.
再帰的に呼び出された関数の結果がtrueであれば、可能な方法があることを示し、したがって関数を終了し、そうでなければi+1番目のケーキを再確認し、方法を探す.
最終的に検索結果に基づいて答え配列を出力し、検索結果に実行可能な方法がない場合、出力−1は終了する.

コード#コード#

#include <iostream>
#include <vector>

using namespace std;

int N;
bool visited[1001][10] = {false};

vector<vector<int>> riceCake;
vector<int> answer;

bool dfs(int before, int day){
    if (day == N){  // 마지막 날에 먹을 떡 고르기!
        for (int i = 0; i < riceCake[day-1].size(); ++i) {
            if (before != riceCake[day-1][i]){
                answer[day-1] = riceCake[day-1][i];
                return true;
            }
        }
    }


    for (int i = 0; i < riceCake[day-1].size(); ++i) {
        int next = riceCake[day-1][i]; // 먹을 떡

        if (before != next && !visited[day+1][next]){  // 이 떡을 먹은 경우를 아직 확인하지 않았다면
            visited[day+1][next] = true;
            answer[day-1] = next;
            if(dfs(next, day+1)){
                return true;
            }
        }
    }

    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N;
    answer.assign(N, 0);

    int count;
    for (int i = 0; i < N; ++i) {
        cin>>count;
        int num;
        vector<int> cakes;
        for (int j = 0; j < count; ++j) {
            cin>>num;
            cakes.push_back(num);
        }
        riceCake.push_back(cakes);
    }

    if (dfs(0, 1)){
        for (int i = 0; i < N; ++i) {
            cout<<answer[i]<<'\n';
        }
    }else{
        cout<<-1;
    }

    return 0;
}

いつでも問題を解くのは簡単そうに見えますが、うーん、DFS探索の練習をしなければなりません.
私はできると思いますが、どうしてできないのか、悲しいです.

reference

【白俊】16432打餅行商人とトラ