[C++] 백준 1516 - 게임 개발

0. [c++] 백준

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

1. 풀이

이번 문제는 이전에 풀어보았던 ACM Craft와 정말 비슷하다는 생각이 들었다.(https://kyunstudio.tistory.com/65)

이전에 이걸 풀때는 시간이 꽤나 걸렸었는데, 이번에는 꽤나 수월하게 풀 수 있었다.

이번에는 BFS를 활용하여 탐색을 하며, 이번의 값은 탐색을 한 값 중에서 가장 큰 값에 자기 자신을 더해서 반환하는 형태로 구현을 해보았다. 

뭐, 이렇게 구현하니까 풀이가 끝났다.

+) 근데, 폰에서 블로그를 보는데 코드가 스크롤이 안되고 자꾸 짤려서 보이던데, 이걸 어떻게 해결해야될려나

음.... 이전 코드들은 문제없이 스크롤 되던데 왜이러는걸까

2. 소스코드

#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
int Time[501];
vector<int> NeedHere[501];
int cache[501];
bool visited[501];
 
int Max(int a, int b) {
    return a > b ? a : b;
}
 
//int DFS(int Here) {
//    int& ret = cache[Here];
//    visited[Here] = true;
//    if (ret != 0) {
//        for (int i = 0; i < NeedHere[Here].size(); i++) {
//            int there = NeedHere[Here][i];
//            if (visited[there])
//                ret -= Time[there];
//            else
//                visited[there] = true;
//        }
//        return ret;
//        
//    }
//    
//    for (int i = 0; i < NeedHere[Here].size(); i++) {
//        int there = NeedHere[Here][i];
//        if(!visited[there])
//            ret += DFS(there);
//    }
//
//    return ret += Time[Here];
//}
 
 
//지금 해야하는 목표
//두가지 노드로 갈라지면 두개를 각각 더하는 것이 아니라
//노드 중 더 큰 값을 반환해야한다.
int BFS(int N) {
    int& ret = cache[N];
    if (ret != 0)
        return ret;
    for (int i = 0; i < NeedHere[N].size(); i++) {
        int there = NeedHere[N][i];
        ret = Max(ret, BFS(there));
    }
 
    return ret += Time[N];
}
 
 
 
 
int main() {
    int N,a;
 
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> Time[i];
        cin >> a;
        while (a != -1) {
            NeedHere[i].push_back(a);
            cin >> a;
        }
    }
 
    /*for (int i = 1; i <= N; i++) {
        memset(visited, false, sizeof(visited));
        cout << DFS(i) << endl;
    }*/
 
    for (int i = 1; i <= N; i++) {
        cout << BFS(i) << endl;
    }
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!